MDSR Ch 8: Supervised Learning

ddir

Announcements

Ch 8 & Ch 9 exercises assigned (due 2/24)
midterm exam plan
- mix of in-class and take-home
- written, in-class portion on Wed 2/27
- take-home portion due Fri 3/1 at 11:59pm
- class will not meet on Friday 3/1
Ch 8 programming notebook assigned
Census Modeling mini-project assigned
- watch out for recent changes to Census wikipedia page

MDSR Ch 8 Errata / Tips

p. 177: include the code chunk at the bottom of the page
- there’s no error, but you need to run the plot and text functions together
- note: the resulting tree is NOT printed in the MDSR book
p. 179: watch out for the leading spaces in relationship and education
p. 200: use mtry = 2 # MDSR book says mtry = 3, think about why 3 doesn’t work…

“Learning”

Supervised Learning

How you learned colors as a child
Requires labeled data (lots of it)

Reinforcement Learning

How you learned to walk
Requires goals (maybe long term, i.e. arbitrary delays between action and reward)

Unsupervised Learning

(Maybe) How you learned to see?
- edge detection, feature recognition, etc?
- who knows…
Search for patterns among unlabeled data

Statistical Learning

statistical learning refers to a set of approaches for estimating the systematic information that X’s (explanatory variables) provide about Y (response variable)
Typical distinction between Supervised and Unsupervised learning
- Supervised learning predictive or inferential modeling
  - there is a response variable (Y)
  - predictive modeling: we want to anticipate the response (Y) ahead of time based on knowledge of a set of measurable inputs (X’s)
  - inferential modeling: we want to understand the way our response (Y) changes as the explanatory variables (X’s) change
  - examples: linear regression & logistic regression are classical examples (we’ll meet others)
- Unsupervised learning methods could be considered “data discovery” models
  - there is NO response variable (Y)
  - we are interested in exposing interesting relationships/groups/clusters among several explanatory variables (X’s)

Regression vs Classification

there’s also a tendency to make distinctions among approaches based on the type of the response (Y) variable
- Regression problems frequently involve to Quantitative/Continuous response
- Classification problems frequently involve to Categorical/Qualitative response
there are certainly exeptions…
- some methods can be reasonably interpreted in both ways
- some methods (e.g., K-nearest neighbors) can be used with either quantitative and categorical response

Health Evaluation and Linkage to Primary Care Study

RQ: What risk factors are associated with serious thoughts of suicide?

`HELPstudy` Data

The HELP study was a randomized controlled clinical trial for adult inpatients with a history of susbstance abuse. Participants were recruited from a detoxification unit in the Boston area.
Inclusion critera:
- adults,
- Spanish or English language proficiency
- reported alcohol, heroin, or cocaine as their first or second drug of choice
- resided in proximity to the primary care clinic to which they would be referred or were homeless.
Exclusion criteria:
- Patients with established primary care relationships they planned to continue
- significant dementia
- specific plans to leave the Boston area that would prevent research participation
- failure to provide contact information for tracking purposes
- pregnancy
Procedure:
- Patients with no primary care physician were randomized to receive a multidisciplinary assessment and a brief motivational intervention or usual care, with the goal of linking them to primary medical care.
- Subjects were interviewed at baseline during their detoxification stay
- follow-up interviews were undertaken every 6 months for 2 years.
- A variety of continuous, count, discrete, and survival time predictors and outcomes were collected at each of these five occasions.

Variables of interest

suicide (response; {“no”, “yes”}): experienced serious thoughts of suicide in last 30 days (measured at baseline)
cesd: Center for Epidemiologic Studies Depression measure at baseline (high scores indicate more depressive symptoms)
sex: male or female
avgAlcohol: average number of drinks (standard units) consumed per day, in the past 30 days (measured at baseline)
pss_fr: perceived social support by friends (measured at baseline, higher scores indicate more support)
treat randomized to HELP clinic: no yes

```r
```r
HELPstudy <- 
  HELPrct %>%
  select(suicide = g1b, age, cesd, sex, avgAlcohol = i1, pss_fr)
# inspect data
glimpse(HELPstudy)

Observations: 453
Variables: 6
$ suicide    <fct> yes, yes, no, no, no, no, yes, yes, no, no, no, no, no, no, no, yes, no, yes, yes, no, no, …
$ age        <int> 37, 37, 26, 39, 32, 47, 49, 28, 50, 39, 34, 58, 58, 60, 36, 28, 35, 29, 27, 27, 41, 33, 34,…
$ cesd       <int> 49, 30, 39, 15, 39, 6, 52, 32, 50, 46, 46, 49, 22, 36, 43, 35, 19, 40, 52, 37, 35, 18, 36, …
$ sex        <fct> male, male, male, female, male, female, female, male, female, male, female, female, male, m…
$ avgAlcohol <int> 13, 56, 0, 5, 10, 4, 13, 12, 71, 20, 0, 13, 20, 13, 51, 0, 0, 1, 9, 23, 26, 0, 34, 4, 6, 3,…
$ pss_fr     <int> 0, 1, 13, 11, 10, 5, 1, 4, 5, 0, 0, 13, 13, 1, 1, 7, 9, 1, 13, 11, 8, 14, 10, 6, 6, 3, 6, 4…

Data Preparation

Training, (query), and test sets
Q: Why partition the data this way?
- explain how the code accomplishes this

```r
```r
# set RNG seed for reproducible results
set.seed(538) 
# partition the data
n <- nrow(HELPstudy)
test_idx <- sample.int(n, size = round(0.25 * n)) # select row numbers for the test set
train <- HELPstudy[-test_idx, ]  # exclude the test set cases
nrow(train)

[1] 340

```r
```r
test <- HELPstudy[test_idx, ]    # test set cases only
nrow(test)

[1] 113

Training & Test sets

if our goal is prediction or inference we need to be disciplined
1. Each observation can either be used for exploration or confirmation, not both.
2. You can use a case as often as you like for exploration, but only once for confirmation.
As soon as you use an observation twice, you’ve switched from confirmation to exploration. NO CHEATING.
- we’ll only use the training data (train) for model building
- we want to preserve the integrity of the test set as a means to validate model accuracy
- we didn’t use a “query” set here
the real test of your model is it’s out-of-sample performance
- this is what we want the test set for
- if your out of sample performance is bad you might want to fix it and try again… but you’re sort of stuck (see #2)
this is where a separate “query” set partition is handy
- provides a practice data set for out of sample performance without jeopardizing the integrity of the test set
- particuluarly useful for models that depend on user-specified “hyperparameters” like regularization/shrinkage (coming up later) or Bayesian methods

Inspecting the `HELPstudy` (training) data

we’re cutting EDA to the bone to be economical with lecture time & slides, but you need to do a careful EDA of your data before you start modeling.
careful EDA in the beginning will save you headaches & wasted time later
you should also to plot your data several ways
- try and come as close as possible to answering your research question
- try and expose issues in the data that will impact modeling decisions

```r
```r
# short (insufficient) EDA
tally(~ suicide, data = train)

suicide
 no yes 
247  93

```r
```r
favstats(~ age, data = train)

favstats(~ cesd, data = train)

```r
```r
tally(~ sex, data = train)

sex
female   male 
    85    255

```r
```r
favstats(~ avgAlcohol, data = train)

ABCDEFGHIJ0123456789

	min <dbl>	Q1 <dbl>	median <dbl>	Q3 <dbl>	max <dbl>	mean <dbl>	sd <dbl>	n <int>	missing <int>
	19	30	34	40	59	35.35588	7.499054	340	0

```r
```r
favstats(~ pss_fr, data = train)

ABCDEFGHIJ0123456789

	min <dbl>	Q1 <dbl>	median <dbl>	Q3 <dbl>	max <dbl>	mean <dbl>	sd <dbl>	n <int>	missing <int>
	1	24	34	41	60	32.50294	12.76275	340	0

```r
```r
# single plot; ugly, but possibly useful (you can do better)
pairs(train)

ABCDEFGHIJ0123456789

	min <dbl>	Q1 <dbl>	median <dbl>	Q3 <dbl>	max <dbl>	mean <dbl>	sd <dbl>	n <int>	missing <int>
	0	3	13	26	134	17.17059	18.76906	340	0

ABCDEFGHIJ0123456789

	min <dbl>	Q1 <dbl>	median <dbl>	Q3 <dbl>	max <dbl>	mean <dbl>	sd <dbl>	n <int>	missing <int>
	0	3	7	10	14	6.802941	4.010237	340	0

Null model

this establishes a useful baseline
with no other information at all, we would be correct about 72% of the time by just assuming that none of these people ever had serious thoughts of suicide.

```r
```r
mod_null <- tally(~ suicide, data = train, format = \percent\)
mod_null

suicide
   no   yes 
72.65 27.35

Decision Trees

CART: classification and regression trees
tree-like flow chart that assigns class labels to individual observations
number of possible trees grows exponentially as number of X’s increases
we’ll use recursive partitioning to produce increasingly “pure” subsets

credit: https://newonlinecourses.science.psu.edu/stat555/node/100/

Decision tree (simple)

consider a simple tree that predicts suicide from just cesd (a depression score)
the tree shows successive partitioning to produce increasingly pure subsets

```r
```r
require(rpart)
rpart(suicide ~ cesd, data = train)

n= 340 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

 1) root 340 93 no (0.7265 0.2735)  
   2) cesd< 34.5 183 24 no (0.8689 0.1311) *
   3) cesd>=34.5 157 69 no (0.5605 0.4395)  
     6) cesd< 54.5 147 60 no (0.5918 0.4082)  
      12) cesd>=45.5 46 14 no (0.6957 0.3043) *
      13) cesd< 45.5 101 46 no (0.5446 0.4554)  
        26) cesd< 41.5 78 31 no (0.6026 0.3974) *
        27) cesd>=41.5 23  8 yes (0.3478 0.6522) *
     7) cesd>=54.5 10  1 yes (0.1000 0.9000) *

visualize first split for depression & suicide ideation model

clearly not perfect…
- depression scores lower than the split are more confidently classified as “no”
- above the split is still very hard to tell
- Q: So, is this single cut score useful?

```r
```r
split <- 34.5 # first split from simple `rpart`
train %>%
  mutate(elevated_depression = cesd >= split) %>%
  ggplot(aes(x = cesd, y = suicide)) + 
  geom_point(aes(color = elevated_depression), 
             position = position_jitter(width = 0, height = 0.15), 
             alpha = 0.4) + 
  geom_vline(xintercept = split, color = \blue\, lty = 2)

Decision tree (complete)

we’re going to reuse the model formula a lot, so MDSR stores the formula form
- form <- as.formula("suicide ~ age + cesd + sex + avgAlcohol + pss_fr")
- this is identical to suicide ~ . since we’re using all the variables in train

```r
```r
mod_tree <- rpart(suicide ~ ., data = train)
mod_tree

n= 340 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

  1) root 340 93 no (0.7265 0.2735)  
    2) cesd< 34.5 183 24 no (0.8689 0.1311) *
    3) cesd>=34.5 157 69 no (0.5605 0.4395)  
      6) cesd< 54.5 147 60 no (0.5918 0.4082)  
       12) avgAlcohol< 25.5 102 34 no (0.6667 0.3333)  
         24) age>=33.5 49 10 no (0.7959 0.2041) *
         25) age< 33.5 53 24 no (0.5472 0.4528)  
           50) avgAlcohol< 2.5 19  6 no (0.6842 0.3158) *
           51) avgAlcohol>=2.5 34 16 yes (0.4706 0.5294)  
            102) cesd< 41.5 24 10 no (0.5833 0.4167) *
            103) cesd>=41.5 10  2 yes (0.2000 0.8000) *
       13) avgAlcohol>=25.5 45 19 yes (0.4222 0.5778)  
         26) pss_fr>=8.5 13  4 no (0.6923 0.3077) *
         27) pss_fr< 8.5 32 10 yes (0.3125 0.6875)  
           54) sex=male 22 10 yes (0.4545 0.5455)  
            108) pss_fr>=1.5 14  6 no (0.5714 0.4286) *
            109) pss_fr< 1.5 8  2 yes (0.2500 0.7500) *
           55) sex=female 10  0 yes (0.0000 1.0000) *
      7) cesd>=54.5 10  1 yes (0.1000 0.9000) *

Decision tree (partykit)

```r
```r
require(partykit)
plot(as.party(mod_tree))

Branching and pruning

the algorithm considers many possible splits (new branches), but prunes them if they don’t sufficiently improve the predictive power of the model (i.e. bear fruit)
a complexity parameter is used to control whether to keep or prune possible splits
printcp prints a table of optimal prunings based on the complexity parameter

```r
```r
printcp(mod_tree)


Classification tree:
rpart(formula = suicide ~ ., data = train)

Variables actually used in tree construction:
[1] age        avgAlcohol cesd       pss_fr     sex       

Root node error: 93/340 = 0.27

n= 340 

     CP nsplit rel error xerror  xstd
1 0.043      0      1.00    1.0 0.088
2 0.022      4      0.78    1.0 0.089
3 0.011      7      0.72    1.0 0.089
4 0.010      9      0.70    1.1 0.090

Model accuracy: Confusion matrix

```r
```r
train_tree <- 
  train %>%
  mutate(suicide_dtree = predict(mod_tree, type = \class\))
confusion <- tally(suicide_dtree ~ suicide, data = train_tree, format = \count\)
confusion

             suicide
suicide_dtree  no yes
          no  242  60
          yes   5  33

it’s important to scrutinize the outcomes predicted by the model against outcomes observed in the data
in this way, the response variable “supervises” our model
confusion matrix is a simple, but useful, tool for this purpose
- each type of classification and misclassification is represented
- model accuracy: correct / total
- model sensitivity is the true positive rate
- model specificity is the true negative rate
Q: How do we know if it’s any good though?

```r
```r
# decision tree model accuracy
dtree_acc <- sum(diag(confusion)) / nrow(train) * 100
dtree_acc

[1] 80.88

Changing the control parameter

Q: What do you think happens if we change the control parameter?
- will the model will be more & less complex?
- which do you think the model will be more “accurate”?

```r
```r
# different control parameter for comparison
mod_tree2 <- rpart(suicide ~ ., data = train, control = rpart.control(cp = 0.03))
plot(as.party(mod_tree2))

```r
```r
train_tree2 <- 
  train %>%
  mutate(suicide_dtree = predict(mod_tree2, type = \class\))
confusion <- tally(suicide_dtree ~ suicide, data = train_tree2, format = \count\)
confusion

             suicide
suicide_dtree  no yes
          no  236  62
          yes  11  31

```r
```r
sum(diag(confusion)) / nrow(train) * 100

[1] 78.53

Optimal decision tree

Hayafil & Rivest (1976) proved that an efficient algorithm to determine the optimal decision tree almost certainly does not exist
- decision tree optimization is NP-complete
- NP: result can be checked quickly with an algorithm (e.g., polynomial time)
- P: problems that can be solved quickly with an algorithm (e.g., polynomial time)
- some problems seem to be easy to check (NP) but NOT necessarily easy to solve (P), like Sudoku puzzles
- P vs NP: are all problems in NP also in P?
- most computer scientists suspect $P \ne NP$ , but it hasn’t been proven (yet)
- there’s a handsome bounty if either way is proven
  - Millenium Prize problems
  - one of seven open problems with $1 million (US) reward for solution!
  - one prize has already been claimed, so act now while supplies last!
Q: Any ideas how we can improve results for our tree?

Forests

a forest is a collection of trees[citation needed].

Random Forests

a random forest is a collection of decision trees.
we more or less bootstrap the decision trees and defer to the majority
procedure:
1. choose number of trees to “grow” (ntree argument) AND the number of variables to consider in each tree (mtry argument)
2. sample the cases in the data with replacement
3. randomly select mtry of the explanatory variables at each split
4. build (grow?) a decision tree on the resulting data
5. repeat ntree times
this bootstrap aggregration is sometimes called bagging
predictions are based on majority rule from all the trees in the forest
- ntree shouldn’t be too small… but can be computationally intensive
- mtry defaults to $\sqrt{p}$ for classification trees and $p / 3$ for regression trees

```r
```r
require(randomForest)
mod_forest <- randomForest(suicide ~ ., data = train, ntree = 2000, mtry = 2)
mod_forest


Call:
 randomForest(formula = suicide ~ ., data = train, ntree = 2000,      mtry = 2) 
               Type of random forest: classification
                     Number of trees: 2000
No. of variables tried at each split: 2

        OOB estimate of  error rate: 28.82%
Confusion matrix:
     no yes class.error
no  213  34      0.1377
yes  64  29      0.6882

```r
```r
# note the built-in confusion matrix
rf_acc <- sum(diag(mod_forest$confusion)) / nrow(train) * 100
rf_acc

[1] 71.18

Bagging

Bagging
- Procedure:
  - create multiple copies of the original training data set using the bootstrap
  - fit a separate decision tree to each copy
  - combine all of the trees in order to create a single predictive model
- on average, each bagged tree only makes use of about 2/3 of the training data
- out-of-bag (OOB) error is like a free query set based on predictions of the samples NOT chosen for a particular tree
selecting a random subset of the variables is an improvement of random forests over bagged trees in general in order to decorrelate the trees

Random Forests (importance)

importance is a metric useful to assess which variables are consistently influential
not as formal as a p-value for significance
- depression score (cesd) appears most important
- sex least important
- other variables somewhere in between
the Gini coefficient measures the purity of a set of candidate child notes

```r
```r
require(tibble)
importance(mod_forest) %>%
  as.data.frame() %>%
  rownames_to_column() %>%  # handy function from `tibble` package
  arrange(desc(MeanDecreaseGini))

ABCDEFGHIJ0123456789

rowname <chr>	MeanDecreaseGini <dbl>
cesd	43.913571
avgAlcohol	32.542581
age	28.755754
pss_fr	21.887942
sex	5.298385

Boosting

Boosting works similar to bagging, except trees are grown sequentially: each tree is grown using information from previously grown trees.
Boosting does not involve bootstrap sampling; each tree is fit on a modified version of the original data set
Boosting learns slowly by prioritizing the hard examples that were fit poorly in the previous model
Because the growth of a particular tree takes into account the other trees that have already been grown, smaller trees are typically sufficient and aids in interpretability.

```r
```r
require(gbm)
# response must be converted to 0/1
train_boost <- 
  train %>%
  mutate(suicide01 = if_else(suicide == \yes\, 1, 0)) %>%
  select(-suicide)
mod_boost <- gbm(suicide01 ~ ., distribution = \bernoulli\,   # because it's a classifier model
                     data = train_boost, n.trees = 3000, interaction.depth = 2) 
# the relative influence is similar to importance result earlier
msummary(mod_boost)

ABCDEFGHIJ0123456789

	var <chr>	rel.inf <dbl>
cesd	cesd	33.503692
age	age	25.003537
avgAlcohol	avgAlcohol	24.544282
pss_fr	pss_fr	14.105824
sex	sex	2.842664

K-Nearest Neighbor

simple method that attempts to predict without constructing a “model”
procedure:
- calculate the distance between pairs of points in the p-dimensional space (defined by our p explanatory variables)
- nearest neighbor classifiers simply assume that observations that are “close” to one another probably have similar outcomes (class membership).
we’ll use Euclidean distance, but this means we can only use quantitative variables (we have to drop sex)

image credit: James et al (2013) http://www-bcf.usc.edu/~gareth/ISL/

KNN classifier

KNN classifiers don’t need to process the training data first, it can happen on the fly
- they’re fast & easy to understand
- can be adversely impacted if a wider scale of one variable dwarfs a narrow scale of another variable in the distance calculation
we’ll restrict to the training data (only) because we still don’t want to look at the test set yet
note: cl = train$suicide as the supervising variable (from train, not train_quant)

```r
```r
require(class)
train_quant <- 
  train %>%
  select(age, cesd, avgAlcohol, pss_fr)
# KNN classifier
suicide_knn <- knn(train = train_quant, test = train_quant, cl = train$suicide, k = 5)
# confusion matrix
confusion <- tally(suicide_knn ~ suicide, data = train, format = \count\)
confusion

           suicide
suicide_knn  no yes
        no  232  55
        yes  15  38

```r
```r
knn_acc <- sum(diag(confusion)) / nrow(train) * 100
knn_acc

[1] 79.41

How (not) to choose k?

Q: what’s wrong with this picture?
- which value of “k” has the best performance?

```r
```r
knn_error_rate <- function(x, y, numNeighbors, z = x) {
  # purpose: fit knn classifier and return proportion of misclassifications
  # inputs: 
  ### x: training data
  ### y: true classifcations from data
  ### numNeighbors: number of nearest neighbors for classifier
  ### z: test data (default to training data)
  y_hat <- knn(train = x, test = z, cl = y, k = numNeighbors)
  return(sum(y_hat != y) / nrow(x))
}
ks <- c(1:15, 20, 25, 30, 40, 50)
train_rates <- sapply(ks, FUN = knn_error_rate, x = train_quant, y = train$suicide)
knn_error_rates <- data.frame(k = ks, 
                              train_rate = train_rates)
knn_error_rates %>%
  ggplot(aes(x = k, y = train_rate)) + 
  geom_point() + 
  geom_line() + 
  ylab(\Misclassification Rate\)

choice of k

Q: how would you characterize performance of each model?
- we have two quantitative variables and a binary response (orange; blue)
- the dashed line is optimal
- the training data plotted
- left side shows K = 1; right side K = 100
- color shows predictions for each KNN classifier in the data space

image credit: James et al (2013) http://www-bcf.usc.edu/~gareth/ISL/

Naive Bayes

aliases
- independence Bayes
- simple Bayes
Naive?
- due to possibly simplistic assumption that explanatory variables are conditionally independent
- conditional independence: $X_1$ and $X_2$ are conditionally independent given $Y$ if, $P(X_1 | X_2 Y) = P(E_1 | Y)$ or equivalently $P(X_1 X_2 | Y) = P(X_1 | Y) P(X_2 | Y)$
- conditional independence means the two explanatory variables are independent given knowledge of $Y$ , but this doesn’t necessarily mean they are independent of one another (or uncorrelated)
- see STAT 318/414 for more on conditional independence

Bayes Theorem:

$\text{Pr}(y|x) = \frac{\text{Pr}(xy)}{\text{Pr}(x)} = \frac{\text{Pr}(x|y)\text{Pr}(y)}{\text{Pr}(x)}$

P(`suicide` = “yes” | `sex` = “male”)

$\text{Pr}(y|x) = \frac{\text{Pr}(xy)}{\text{Pr}(x)} = \frac{\text{Pr}(x|y)\text{Pr}(y)}{\text{Pr}(x)}$

consider the first person in our training set
let’s calculate $P(\text{suicide} | \text{male})$ , then
- $y$ is suicide == "yes"
- $x$ is sex == "male"

```r
```r
head(train, 1)

tally(sex ~ suicide, data = train, margins = TRUE)

        suicide
sex       no yes
  female  53  32
  male   194  61
  Total  247  93

```r
```r
tally( ~ sex, data = train, margins = TRUE)

sex
female   male  Total 
    85    255    340

```r
```r
tally( ~ suicide, data = train, margins = TRUE)

suicide
   no   yes Total 
  247    93   340

ABCDEFGHIJ0123456789

	suicide <fctr>	age <int>	cesd <int>	sex <fctr>	avgAlcohol <int>	pss_fr <int>
3	no	26	39	male	0	13

P(`suicide` = “yes” | `sex` = “male”)

$P(\text{suicide} | \text{male}) = \frac{P(\text{male}|\text{suicide})P(\text{suicide})}{P(\text{male})} = \frac{(61/93)(93/340)}{(255/340)} = \frac{0.18}{0.75} = 0.24$

For those in HELPrct population, the probability of serious thoughts of suicide given (only) that the person is male is 0.24
This only allowed us to take one variable (sex) into consideration
a Naive Bayes classifier extends to additional variables by assuming conditional independence

Naive Bayes

Q: How did we do?

```r
```r
require(e1071)  # awful name for a package...
mod_nb <- naiveBayes(suicide ~ ., data = train)
suicide_nb <- predict(mod_nb, newdata = train)
confusion <- tally(suicide_nb ~ suicide, data = train, format = \count\)
confusion

          suicide
suicide_nb  no yes
       no  224  62
       yes  23  31

```r
```r
nb_acc <- sum(diag(confusion)) / nrow(train) * 100
nb_acc

[1] 75

Artificial Neural Networks

useful to think of a neural network according to layers of information processing
every neural network has one input layer with nodes corresponding to each input variable (including indicators for factors)
every neural network has one output layer (often one node)
a neural network can have one or more hidden layers that reconcile patterns from the inputs that correspond to outputs
- guidance available on when a neural network benefits from multiple hidden layers
- guidance available on size of hidden layer(s)
the algorithm essentially searches for an optimal set of weights corresponding to edges between all pairs of nodes in successive layers (input >> hidden(s) >> output)

```r
```r
require(nnet)
mod_nnet <- nnet(suicide ~ ., data = train, size = 8)

# weights:  57
initial  value 230.113258 
iter  10 value 177.092442
iter  20 value 169.786429
iter  30 value 165.360178
iter  40 value 163.286366
iter  50 value 160.656488
iter  60 value 156.073589
iter  70 value 153.980013
iter  80 value 153.830620
final  value 153.830466 
converged

```r
```r
suicide_nn <- predict(mod_nnet, newdata = train, type = \class\)
confusion <- tally(suicide_nn ~ suicide, data = train, format = \count\)
confusion

          suicide
suicide_nn  no yes
       no  236  59
       yes  11  34

```r
```r
nnet_acc <- sum(diag(confusion)) / nrow(train) * 100
nnet_acc

[1] 79.41

```r
```r
# Plotting artificial neural networks (no plotting function in `nnet` package)
# import function from Github 
library(devtools)
source_url('https://gist.githubusercontent.com/fawda123/7471137/raw/466c1474d0a505ff044412703516c34f1a4684a5/nnet_plot_update.r')

SHA-1 hash of file is 74c80bd5ddbc17ab3ae5ece9c0ed9beb612e87ef

```r
```r
# plot ANN
plot.nnet(mod_nnet)

Loading required package: reshape
there is no package called ‘reshape’

Logistic regression model

```r
```r
# logistic
mod_logit <- glm(suicide ~ ., data = train, family = \binomial\)
msummary(mod_logit)

Coefficients:
            Estimate Std. Error z value Pr(>|z|)    
(Intercept) -1.60519    0.86254   -1.86    0.063 .  
age         -0.03458    0.01854   -1.86    0.062 .  
cesd         0.06333    0.01259    5.03  4.9e-07 ***
sexmale     -0.46303    0.30584   -1.51    0.130    
avgAlcohol   0.01496    0.00691    2.17    0.030 *  
pss_fr      -0.04799    0.03408   -1.41    0.159    

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 398.98  on 339  degrees of freedom
Residual deviance: 345.44  on 334  degrees of freedom
AIC: 357.4

Number of Fisher Scoring iterations: 4

```r
```r
suicide_logitProb <- predict(mod_logit, newdata = train, type = \response\)
suicide_logit <- ifelse(suicide_logitProb > 0.5, yes = \yes\, \no\)
confusion <- tally(suicide_logit ~ suicide, data = train, format = \count\)
confusion

             suicide
suicide_logit  no yes
          no  229  69
          yes  18  24

```r
```r
logit_acc <- sum(diag(confusion)) / nrow(train) * 100
logit_acc

[1] 74.41

Aside: Support Vector Machines

image credit: James et al (2013) http://www-bcf.usc.edu/~gareth/ISL/

Support vector machines are another group of classification models that attempt to define a mathematical boundary between two classes
- maximal margin classifier: if possible to identify a line, or plane, (or hyperplane) that perfectly separates the two classes…
  - we choose the boundary that maximizes separation
  - the (few) points that define the boundary are the so-called “support vectors”, other points don’t impact position of the boundary
  - very sensitive to a few influential points
- support vector classifier: extension of MMC that permits a “soft margin”
  - still a line/plane/hyperplane, but a margin of “tolerance” is permitted
  - improves robustness to individual observations
  - support vectors are defined by any observations on the wrong side of the margin for their class (those beyond the margin still don’t affect SVC)
- support vector machine: extension of SVC that permits a non-linear decision boundary methods
As a technical point, SVMs tend to give fairly similar results to logistic regression
- When classes are well-separated, SVM may be preferred
- With more overlapping regimes, logistic regression is often preferred

```r
```r
require(e1071)  # again, awful name for a package...
# mod_svm = svm(suicide ~ ., data = train, kernel = \linear\, cost = 10, scale = FALSE)
mod_svm = svm(suicide ~ ., data = train, kernel = \radial\, cost = 10, scale = FALSE)
print(mod_svm)


Call:
svm(formula = suicide ~ ., data = train, kernel = \radial\, cost = 10, scale = FALSE)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  radial 
       cost:  10 
      gamma:  0.1667 

Number of Support Vectors:  340

```r
```r
suicide_svm <- predict(mod_svm, newdata = train)
confusion <- tally(suicide_svm ~ suicide, data = train, format = \count\)
confusion

           suicide
suicide_svm  no yes
        no  247   0
        yes   0  93

```r
```r
svm_acc <- sum(diag(confusion)) / nrow(train) * 100
svm_acc

[1] 100

How have we done so far?

We need some way to compare and evaluate models (we’ll formalize this in a moment)
Q: which model would you choose?
Q: how do you know which result(s) to trust?

```r
```r
# summary of results
ModelComparison <- 
  tribble(
  ~model, ~accuracy, 
  \**NULL MODEL**\, mod_null[1], 
  \decision tree\, dtree_acc, 
  \random forest\, rf_acc, 
  \k-nearest neighbors\, knn_acc, 
  \naive Bayes\, nb_acc, 
  \neural network\, nnet_acc, 
  \logistic regression\, logit_acc
)
ModelComparison %>%
  arrange(desc(accuracy))

ABCDEFGHIJ0123456789

model <chr>	accuracy <dbl>
decision tree	80.88235
k-nearest neighbors	79.41176
neural network	79.41176
naive Bayes	75.00000
logistic regression	74.41176
NULL MODEL	72.64706
random forest	71.17647

Ensemble methods

we have several possibly legitimate models that take a different approach to our classification problem
if each model has taken an independent approach, there’s a clear benefit to combining them
e.g., if $\epsilon_i$ is the error rate of model $i$ , then the chance that all 5 models misclassify a case is smaller than the error rate for any individual since $\prod_{i=1}^{k}\epsilon_i$ and $\epsilon_i < 1$ for any $i$
- we exclude the null model & replace the decision tree with random forest model
- Q: what do we achieve with different values for vote?

```r
```r
vote <- 3
suicide_ensemble <- 
  ifelse((suicide_knn   == \yes\) + 
         (suicide_nn    == \yes\) + 
         (suicide_nb    == \yes\) + 
         (suicide_logit == \yes\) + 
         (mod_forest$predicted == \yes\) >= vote, 
         \yes\, \no\)
confusion <- tally(suicide_ensemble ~ suicide, data = train, format = \count\)
confusion

                suicide
suicide_ensemble  no yes
             no  235  62
             yes  12  31

```r
```r
ens_acc <- sum(diag(confusion)) / nrow(train) * 100
# summary of results
ModelComparison <- 
  tribble(
  ~model, ~accuracy, 
  \**NULL MODEL**\, mod_null[1], 
  \random forest\, rf_acc, 
  \k-nearest neighbors\, knn_acc, 
  \naive Bayes\, nb_acc, 
  \neural network\, nnet_acc, 
  \logistic regression\, logit_acc, 
  \**ENSEMBLE**\, ens_acc
)
ModelComparison %>%
  arrange(desc(accuracy))

ABCDEFGHIJ0123456789

model <chr>	accuracy <dbl>
k-nearest neighbors	79.41176
neural network	79.41176
ENSEMBLE	78.23529
naive Bayes	75.00000
logistic regression	74.41176
NULL MODEL	72.64706
random forest	71.17647

Ensemble Models

Ensemble methods are a useful way to hedge our bets
- recall: Random Forest itself is an ensembling of decision trees
- There are often lots of reasonable approaches to modeling a given data set
- Good option for blending several models or the same model with different settings
- Especially useful when models disagree (Q: Why?)
We allowed each model to have an equal “vote”, but a weighted ensemble is a straight-forward extension
SuperLearner package has some nice tools to do this directly
- includes lots of predictive models for classification & regression
- also includes screening models for variable selection
- important SuperLearner calls other packages corresponding to the available methods, and you need to install your own package dependencies to access those methods

```r
```r
require(SuperLearner)
listWrappers()  # list available models in `SuperLearner`

All prediction algorithm wrappers in SuperLearner:
 [1] \SL.bartMachine\      \SL.bayesglm\         \SL.biglasso\         \SL.caret\           
 [5] \SL.caret.rpart\      \SL.cforest\          \SL.dbarts\           \SL.earth\           
 [9] \SL.extraTrees\       \SL.gam\              \SL.gbm\              \SL.glm\             
[13] \SL.glm.interaction\  \SL.glmnet\           \SL.ipredbagg\        \SL.kernelKnn\       
[17] \SL.knn\              \SL.ksvm\             \SL.lda\              \SL.leekasso\        
[21] \SL.lm\               \SL.loess\            \SL.logreg\           \SL.mean\            
[25] \SL.nnet\             \SL.nnls\             \SL.polymars\         \SL.qda\             
[29] \SL.randomForest\     \SL.ranger\           \SL.ridge\            \SL.rpart\           
[33] \SL.rpartPrune\       \SL.speedglm\         \SL.speedlm\          \SL.step\            
[37] \SL.step.forward\     \SL.step.interaction\ \SL.stepAIC\          \SL.svm\             
[41] \SL.template\         \SL.xgboost\         

All screening algorithm wrappers in SuperLearner:
[1] \All\
[1] \screen.corP\           \screen.corRank\        \screen.glmnet\         \screen.randomForest\  
[5] \screen.SIS\            \screen.template\       \screen.ttest\          \write.screen.template\

Model Evaluation

image credit: James et al (2013) http://www-bcf.usc.edu/~gareth/ISL/

We have overfit the data if we allow our model too much flexibility to accommodate the idiosyncrasies of the training data.
It’s an easy trap to stumble into, especially if we fail to preserve a test sample during modeling.
An overfitted model will perform poorly when attempting to predict results for new (i.e. test) data that the model has never seen before.
a few principles for evaluating models
- cross-validation
- measuring prediction error
- Confusion matrices (as we’ve discussed)
- receiver operating characteristic (ROC) curves
- bias-variance tradeoff
Lastly, we’ll also mention regularization as a strategy to protect against overfitting in regression modeling

Cross-validation

we had partitioned our training and test data from the beginning
once we are satisfied with our model, we use the test set to challenge our model to predict results for observations it has not previously encountered
We call this “out-of-sample” testing
Poor performance would suggest that our model has overfit the data
preserving a test set from the beginning is a more pure approach, but compromises are common
- 50-50 cross-validation:
  - Split data in half,
  - Use the first half to predict the second, and vice versa.
  - Evaluate performance. (a.k.a. 2-fold cross-validation)
- k-fold cross validation (see caret package):
  - Split data into k equal partitions.
  - Use each of the k partitions in turn as the “test” set while other $(k - 1)$ partitions are pooled for use as training set.
  - Aggregate the results for all of the k partitions

Prediction error

for quantitative responses, we have several common metrics for assessing predictive performance
- commonly used even when test set is not available (e.g, leave-one-out)
- when applying to test set
Evaluate deviations between observed and predicted values
- RMSE: $\sqrt{\frac{1}{n}\sum(y - \hat{y})^2}$
- MAE: $\frac{1}{n}\sum|y - \hat{y}|$
Correlation: unitless scale (-1, 1) with no correlation near zero, strong positive correlation near 1 (and strong negative near -1)
- (most familiar) Person’s product-moment correlation
- (rank-based alternative) Spearman’s rho
- (rank-based alternative) Kendall’s tau
$R^2$ : coefficient of determination–proportion of response variability explained by the model–0 for none at all; 1 for perfect prediction

Confusion matrix

we’ve discussed quite a few confusion matrices while assessing model performance when classifying our training data.
Let’s evaluate the test data…

```r
```r
# k-Nearest Neighbor
test_knn <- knn(train = train_quant, cl = train$suicide, k = 5,
                   test = select(test, age, cesd, avgAlcohol, pss_fr))
confusion <- tally(test_knn ~ suicide, data = test, format = \count\)
confusion # test data

        suicide
test_knn no yes
     no  68  23
     yes 11  11

```r
```r
sum(diag(confusion)) / nrow(test)

[1] 0.6991

Out of sample model comparisons

lots of these models have different classes, but many of them have a predict() method associated

```r
```r
# slight modification of our null model (intercept-only logit model)
mod_null <- glm(suicide ~ 1, data = train, family = \binomial\)
# store our various models as a list
models <- list(mod_null, mod_tree, mod_tree2, mod_forest, mod_nnet, mod_nb, mod_logit)
# # models and various `predict()` methods available
# lapply(models, FUN = class)
# methods(\predict\)

Receiver operating characteristic (ROC) curves

from MDSR Figure 8.6 (p. 191)

We’ve mostly focused on classifications in the context of the actual response (suicide: {“yes”, “no”})
probability associated with each classification is also of value
ROC curves graphically display the trade-off between true-positive and false-positive classifications
Q: How have we done overall?
Q: What would “ideal” look like?

Receiver operating characteristic (ROC) curves

The figure shows predictions of a binary classifier model (e.g., “Yes” or “No” outcome)
Q: In the context of our HELPrct example, what do the two distributions represent?
Q: when is the “ideal” achieved?

image credit (2/13/2019): https://en.wikipedia.org/wiki/Receiver_operating_characteristic

Receiver operating characteristic (ROC) curves

Q: How did our models do?
Q: Which one seems to be the best

```r
```r
require(ROCR)
# output arguments corresponding to objects in `model` list
outputs <- c(\response\, \prob\, \prob\, \prob\, \raw\, \raw\, \response\)
roc_test <- mapply(FUN = predict, models, type = outputs, MoreArgs = list(newdata = test)) %>%
  as.data.frame() %>%
  select(1, 3, 5, 7, 8, 10, 11)
names(roc_test) <- c(\mod_null\, \mod_tree\, \mod_tree2\, \mod_forest\, \mod_nnet\, \mod_nb\, \mod_logit\)
glimpse(roc_test)

Observations: 113
Variables: 7
$ mod_null   <dbl> 0.2735, 0.2735, 0.2735, 0.2735, 0.2735, 0.2735, 0.2735, 0.2735, 0.2735, 0.2735, 0.2735, 0.2…
$ mod_tree   <dbl> 0.1311, 0.4286, 0.1311, 0.1311, 0.1311, 0.1311, 0.4167, 0.1311, 1.0000, 0.1311, 0.1311, 0.4…
$ mod_tree2  <dbl> 0.1311, 0.6875, 0.1311, 0.1311, 0.1311, 0.1311, 0.3333, 0.1311, 0.6875, 0.1311, 0.1311, 0.3…
$ mod_forest <dbl> 0.1635, 0.4665, 0.1430, 0.1660, 0.0210, 0.1960, 0.2450, 0.0305, 0.5415, 0.0535, 0.1835, 0.4…
$ mod_nnet   <dbl> 0.72469, 0.00000, 0.04715, 0.12415, 0.04715, 0.18977, 0.69428, 0.04715, 0.72469, 0.18977, 0…
$ mod_nb     <dbl> 0.48084, 0.97927, 0.14694, 0.43275, 0.05504, 0.11254, 0.20647, 0.01172, 0.81458, 0.06190, 0…
$ mod_logit  <dbl> 0.34117, 0.55543, 0.15191, 0.33218, 0.09026, 0.13946, 0.24992, 0.03694, 0.65802, 0.09861, 0…

```r
```r
roc_tidy <- 
  roc_test %>%
  gather(key = \model\, value = \y_hat\) %>%
  group_by(model) %>%
  dplyr::do(get_roc(., y = test$suicide))
# plot ROC curves
roc_tidy %>%
  ggplot(aes(x = fpr, y = tpr)) + 
  geom_line(aes(color = model)) + 
  geom_abline(intercept = 0, slope = 1, lty = 3) + 
  ylab(\True positive rate (sensitivity)\) + 
  xlab(\False positive rate (1 - specificity)\) + 
  geom_point(data = predictions_summary, size = 3, 
             aes(x = test_fpr, y = test_tpr, color = model))

Bias-variance tradeoff

image credit: James et al (2013) http://www-bcf.usc.edu/~gareth/ISL/

For a given test value, $x_0$ :

$E(y_0 - \hat{f}(x_0))^2 = \text{Var}(\hat{f}(x_0)) + [\text{Bias}(\hat{f}(x_0))]^2 + \text{Var}(\epsilon)$

The expected variability of the test set predictions is a sum of three quantities
- Randomness (from nature; our so-called error term)
- Bias (from under-fitting the data)
- Variance (from over-fitting the data)
Consider the figure above. The Black cubic curve is the true relationship between Y and X used to generate the data.
Bias here refers to the a consistent tendency of a statistical model to over- or under-estimate true population parameters (i.e. the nature of the process that generated the data). In the figure,
- The Orange linear model is highly biased because–roughly speaking–the model
  - consistently over-estimates Y when X is between 0 and 40
  - then consistently underestimates Y for X between 40 and 70
  - and then overestimates Y again for X greater than 70
- In short, the linear model fails to properly reflect the relationship (i.e., conditional expectation) between the response (Y) and the explanatory variables (X’s). As a result, some of the structural relationship between Y and X’s is incorrectly treated like randomness.
- The Green model tends to closely follow the data, so it has lower bias
- In the green wiggly model tends to closely follow the
Variance here refers to how much our model would change if we had estimated it with a different training set. In the figure,
- The Green wiggly model follows the observations too closely
  - If one (or a few) training observations were changed, we expect a substantial impact on the model
- The Orange model would not change much if one or a few training observations were changed, so it has lower variance

Regularization/Shrinkage (Ridge Regression & Lasso)

Goal: sacrifice a small amount of bias to decrease variance
- Especially useful when number of explanatory variables is large (perhaps larger than n!) and/or when parameter estimates have high variance
Method: impose a constraint that intentionally biases parameter estimates (e.g. slopes in regression) toward zero in order to reduce variance
recall: in Regression we fit our model by optimizing some distance metric (e.g., sum of squared errors–SSE)
regularization/shrinkage methods simply modify the quantity that we optimize
- Ridge regression: minimize $\text{SSE} + \lambda \sum_{j = 1}^p \beta_j^2$
- Lasso: minimize $\text{SSE} + \lambda \sum_{j = 1}^p | \beta_j |$
important difference:
- Ridge regression model includes all parameters, so there is no variable selection
- Lasso has built-in variable selection by forcing some of the $\beta_j$ ’s to be exactly zero
Tuning parameter: $\lambda$
- when the tuning parameter $\lambda$ is zero, the result is the usual least squares regression model
- when the tuning parameter $\lambda$ is very large, the result is a null model (intercept only)
- proper selection is important
- cross-validation is a popular method for setting lambda (e.g. leave-one-out)
R function: glmnet::glmnet()
- function argument alpha = 0 for ridge regression
- function argument alpha = 1 for Lasso
- fits linear, logistic, and other regression models

Regularization/Shrinkage (Ridge Regression & Lasso)

Q: What do you note about comparison of coefficient estimates (with logistic model)?

```r
```r
require(glmnet)
train_matrix <- 
  train_quant %>%
  mutate(male = ifelse(train$sex == \male\, 1, 0)) %>%
  as.matrix()
# fit model
mod_lasso <- glmnet(x = train_matrix, y = train$suicide, family = \binomial\, alpha = 1)  
# plot coefficients as a function of \penalty\ imposed by tuning parameter
plot(mod_lasso)

```r
```r
# choosing lambda
cv_result <- cv.glmnet(x = as.matrix(train_quant), y = train$suicide, family = \binomial\, type.measure = \class\)
plot(cv_result)

```r
```r
best_lambda <- cv_result$lambda.min
# lasso coefficient estimates (note shrinkage; sex/female variable dropped)
predict(mod_lasso, type = \coefficients\, s = best_lambda)

6 x 1 sparse Matrix of class \dgCMatrix\
                    1
(Intercept) -2.186379
age         -0.015495
cesd         0.054849
avgAlcohol   0.008302
pss_fr      -0.023553
male        -0.185568

```r
```r
# logistic regression coefficient estimates
msummary(mod_logit)

Coefficients:
            Estimate Std. Error z value Pr(>|z|)    
(Intercept) -1.60519    0.86254   -1.86    0.063 .  
age         -0.03458    0.01854   -1.86    0.062 .  
cesd         0.06333    0.01259    5.03  4.9e-07 ***
sexmale     -0.46303    0.30584   -1.51    0.130    
avgAlcohol   0.01496    0.00691    2.17    0.030 *  
pss_fr      -0.04799    0.03408   -1.41    0.159    

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 398.98  on 339  degrees of freedom
Residual deviance: 345.44  on 334  degrees of freedom
AIC: 357.4

Number of Fisher Scoring iterations: 4

Regularization/Shrinkage (Ridge Regression & Lasso)

Q: What do you note about comparison of training accuracy (with logistic model)?

```r
```r
# training accuracy
suicide_lassoProb <- predict(mod_lasso, s = best_lambda, newx = train_matrix, type = \response\)
suicide_lasso <- ifelse(suicide_lassoProb > 0.5, yes = \yes\, \no\)
confusion <- tally(suicide_lasso ~ suicide, data = train, format = \count\)
confusion

             suicide
suicide_lasso  no yes
          no  239  75
          yes   8  18

```r
```r
lasso_acc <- sum(diag(confusion)) / nrow(train) * 100
# Logistic regression training accuracy with/without regularization
lasso_acc  # Regularization (Lasso)

[1] 75.59

```r
```r
logit_acc  # No regularization

[1] 74.41

LS0tCnRpdGxlOiAiTURTUiBDaCA4OiBTdXBlcnZpc2VkIExlYXJuaW5nIgpvdXRwdXQ6IAogIHNsaWR5X3ByZXNlbnRhdGlvbjogZGVmYXVsdAogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQgIAotLS0KCmRkaXIKCmBgYHtyIEZyb250IE1hdHRlciwgZWNobz1UUlVFLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFLCBpbmNsdWRlPUZBTFNFfQojIGNsZWFuIHVwIFIgZW52aXJvbm1lbnQKcm0obGlzdCA9IGxzKCkpCgojIGdsb2JhbCBvcHRpb25zCmtuaXRyOjpvcHRzX2NodW5rJHNldChldmFsPVRSVUUsIGluY2x1ZGU9VFJVRSkKb3B0aW9ucyhkaWdpdHM9NCkKCiMgcGFja2FnZXMgdXNlZApsaWJyYXJ5KG1kc3IpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KG1vZGVscikKbGlicmFyeShycGFydCkKbGlicmFyeShwYXJ0eWtpdCkKbGlicmFyeShyYW5kb21Gb3Jlc3QpCmxpYnJhcnkoZ2JtKQpsaWJyYXJ5KHRpYmJsZSkKbGlicmFyeShjbGFzcykKbGlicmFyeShlMTA3MSkKbGlicmFyeShubmV0KQpsaWJyYXJ5KFJTTk5TKQpsaWJyYXJ5KGdsbW5ldCkKbGlicmFyeShST0NSKQpsaWJyYXJ5KFN1cGVyTGVhcm5lcikKCiMgdXNlci1kZWZpbmVkIGZ1bmN0aW9ucyAKCmtubl9lcnJvcl9yYXRlIDwtIGZ1bmN0aW9uKHgsIHksIG51bU5laWdoYm9ycywgeiA9IHgpIHsKICAjIHB1cnBvc2U6IGZpdCBrbm4gY2xhc3NpZmllciBhbmQgcmV0dXJuIHByb3BvcnRpb24gb2YgbWlzY2xhc3NpZmljYXRpb25zCiAgIyBpbnB1dHM6IAogICMjIyB4OiB0cmFpbmluZyBkYXRhCiAgIyMjIHk6IHRydWUgY2xhc3NpZmNhdGlvbnMgZnJvbSBkYXRhCiAgIyMjIG51bU5laWdoYm9yczogbnVtYmVyIG9mIG5lYXJlc3QgbmVpZ2hib3JzIGZvciBjbGFzc2lmaWVyCiAgIyMjIHo6IHRlc3QgZGF0YSAoZGVmYXVsdCB0byB0cmFpbmluZyBkYXRhKQogIHlfaGF0IDwtIGtubih0cmFpbiA9IHgsIHRlc3QgPSB6LCBjbCA9IHksIGsgPSBudW1OZWlnaGJvcnMpCiAgcmV0dXJuKHN1bSh5X2hhdCAhPSB5KSAvIG5yb3coeCkpCn0KCmdldF9yb2MgPC0gZnVuY3Rpb24oeCwgeSkgewogICMgcHVycG9zZTogZXh0cmFjdCB0cnVlLXBvc2l0aXZlIHJhdGUgJiBmYWxzZS1wb3NpdGl2ZSByYXRlIGZvciBhcmJpdHJhcnkgY2xhc3NpZmllciBtb2RlbAogICMgaW5wdXRzOiAKICAjIyMgeDogKHByZS1wcm9jZXNzZWQpIGRhdGEgZnJhbWUgd2l0aCB0d28gY29sdW1ucy0tKDEpIGBtb2RlbGAgbmFtZSBhbmQgKDIpIGB5X2hhdGAgZm9yIHRlc3QgcHJlZGljdGlvbnMKICAjIyMgeTogcmVzcG9uc2UgdmVjdG9yIGZyb20gdGVzdCBzZXQKICBwcmVkIDwtIFJPQ1I6OnByZWRpY3Rpb24oeCR5X2hhdCwgeSkKICBwZXJmIDwtIFJPQ1I6OnBlcmZvcm1hbmNlKHByZWQsICd0cHInLCAnZnByJykKICBwZXJmX2RmIDwtIGRhdGEuZnJhbWUocGVyZkB4LnZhbHVlcywgcGVyZkB5LnZhbHVlcykgICMgQCBub3RhdGlvbiBpcyB1bnVzdWFsIChTNCBvYmplY3QpCiAgbmFtZXMocGVyZl9kZikgPC0gYygiZnByIiwgInRwciIpCiAgcmV0dXJuKHBlcmZfZGYpCn0KCgojIGlucHV0cyBzdW1tYXJ5CmRhdGEoIkhFTFByY3QiKQoKYGBgCgoKIyMgQW5ub3VuY2VtZW50cwoKLSBDaCA4ICYgQ2ggOSBleGVyY2lzZXMgYXNzaWduZWQgKGR1ZSAyLzI0KQotIG1pZHRlcm0gZXhhbSBwbGFuCiAgICAtIG1peCBvZiBpbi1jbGFzcyBhbmQgdGFrZS1ob21lCiAgICAtIHdyaXR0ZW4sIGluLWNsYXNzIHBvcnRpb24gb24gV2VkIDIvMjcKICAgIC0gdGFrZS1ob21lIHBvcnRpb24gZHVlIEZyaSAzLzEgYXQgMTE6NTlwbQogICAgLSBjbGFzcyB3aWxsIG5vdCBtZWV0IG9uIEZyaWRheSAzLzEgCi0gQ2ggOCBwcm9ncmFtbWluZyBub3RlYm9vayBhc3NpZ25lZAotIENlbnN1cyBNb2RlbGluZyBtaW5pLXByb2plY3QgYXNzaWduZWQKICAgIC0gd2F0Y2ggb3V0IGZvciByZWNlbnQgY2hhbmdlcyB0byBDZW5zdXMgd2lraXBlZGlhIHBhZ2UgCgojIyMjIE1EU1IgQ2ggOCBFcnJhdGEgLyBUaXBzCgotIHAuIDE3NzogaW5jbHVkZSB0aGUgY29kZSBjaHVuayBhdCB0aGUgYm90dG9tIG9mIHRoZSBwYWdlCiAgICAtIHRoZXJlJ3Mgbm8gZXJyb3IsIGJ1dCB5b3UgbmVlZCB0byBydW4gdGhlIGBwbG90YCBhbmQgYHRleHRgIGZ1bmN0aW9ucyB0b2dldGhlcgogICAgLSBub3RlOiB0aGUgcmVzdWx0aW5nIHRyZWUgaXMgTk9UIHByaW50ZWQgaW4gdGhlIE1EU1IgYm9vawotIHAuIDE3OTogd2F0Y2ggb3V0IGZvciB0aGUgbGVhZGluZyBzcGFjZXMgaW4gYHJlbGF0aW9uc2hpcGAgYW5kIGBlZHVjYXRpb25gCi0gcC4gMjAwOiB1c2UgYG10cnkgPSAyYCAgIyBNRFNSIGJvb2sgc2F5cyBtdHJ5ID0gMywgdGhpbmsgYWJvdXQgd2h5IDMgZG9lc24ndCB3b3JrLi4uCgoKIyMgIkxlYXJuaW5nIgoKIyMjIFN1cGVydmlzZWQgTGVhcm5pbmcKCi0gSG93IHlvdSBsZWFybmVkIGNvbG9ycyBhcyBhIGNoaWxkCi0gUmVxdWlyZXMgbGFiZWxlZCBkYXRhIChsb3RzIG9mIGl0KQoKIyMjIFJlaW5mb3JjZW1lbnQgTGVhcm5pbmcKCi0gSG93IHlvdSBsZWFybmVkIHRvIHdhbGsKLSBSZXF1aXJlcyBnb2FscyAobWF5YmUgbG9uZyB0ZXJtLCBpLmUuIGFyYml0cmFyeSBkZWxheXMgYmV0d2VlbiBhY3Rpb24gYW5kIHJld2FyZCkKCiMjIyBVbnN1cGVydmlzZWQgTGVhcm5pbmcKCi0gKE1heWJlKSBIb3cgeW91IGxlYXJuZWQgdG8gc2VlPyAgCiAgICAtIGVkZ2UgZGV0ZWN0aW9uLCBmZWF0dXJlIHJlY29nbml0aW9uLCBldGM/CiAgICAtIHdobyBrbm93cy4uLgotIFNlYXJjaCBmb3IgcGF0dGVybnMgYW1vbmcgdW5sYWJlbGVkIGRhdGEKCgoKIyMgU3RhdGlzdGljYWwgTGVhcm5pbmcKCi0gc3RhdGlzdGljYWwgbGVhcm5pbmcgcmVmZXJzIHRvIGEgc2V0IG9mIGFwcHJvYWNoZXMgZm9yIGVzdGltYXRpbmcgdGhlIHN5c3RlbWF0aWMgaW5mb3JtYXRpb24gdGhhdCBYJ3MgKGV4cGxhbmF0b3J5IHZhcmlhYmxlcykgcHJvdmlkZSBhYm91dCBZIChyZXNwb25zZSB2YXJpYWJsZSkKLSBUeXBpY2FsIGRpc3RpbmN0aW9uIGJldHdlZW4gKipTdXBlcnZpc2VkKiogYW5kICoqVW5zdXBlcnZpc2VkKiogbGVhcm5pbmcKICAgIC0gKipTdXBlcnZpc2VkKiogbGVhcm5pbmcgcHJlZGljdGl2ZSBvciBpbmZlcmVudGlhbCBtb2RlbGluZwogICAgICAgIC0gdGhlcmUgaXMgYSByZXNwb25zZSB2YXJpYWJsZSAoWSkKICAgICAgICAtIHByZWRpY3RpdmUgbW9kZWxpbmc6IHdlIHdhbnQgdG8gYW50aWNpcGF0ZSB0aGUgcmVzcG9uc2UgKFkpIGFoZWFkIG9mIHRpbWUgYmFzZWQgb24ga25vd2xlZGdlIG9mIGEgc2V0IG9mIG1lYXN1cmFibGUgaW5wdXRzIChYJ3MpCiAgICAgICAgLSBpbmZlcmVudGlhbCBtb2RlbGluZzogd2Ugd2FudCB0byB1bmRlcnN0YW5kIHRoZSB3YXkgb3VyIHJlc3BvbnNlIChZKSBjaGFuZ2VzIGFzIHRoZSBleHBsYW5hdG9yeSB2YXJpYWJsZXMgKFgncykgY2hhbmdlCiAgICAgICAgLSBleGFtcGxlczogbGluZWFyIHJlZ3Jlc3Npb24gJiBsb2dpc3RpYyByZWdyZXNzaW9uIGFyZSBjbGFzc2ljYWwgZXhhbXBsZXMgKHdlJ2xsIG1lZXQgb3RoZXJzKQogICAgLSAqKlVuc3VwZXJ2aXNlZCoqIGxlYXJuaW5nIG1ldGhvZHMgY291bGQgYmUgY29uc2lkZXJlZCAiZGF0YSBkaXNjb3ZlcnkiIG1vZGVscyAKICAgICAgICAtIHRoZXJlIGlzIE5PIHJlc3BvbnNlIHZhcmlhYmxlIChZKQogICAgICAgIC0gd2UgYXJlIGludGVyZXN0ZWQgaW4gZXhwb3NpbmcgaW50ZXJlc3RpbmcgcmVsYXRpb25zaGlwcy9ncm91cHMvY2x1c3RlcnMgYW1vbmcgc2V2ZXJhbCBleHBsYW5hdG9yeSB2YXJpYWJsZXMgKFgncykKCgojIyBSZWdyZXNzaW9uIHZzIENsYXNzaWZpY2F0aW9uCgotIHRoZXJlJ3MgYWxzbyBhIHRlbmRlbmN5IHRvIG1ha2UgZGlzdGluY3Rpb25zIGFtb25nIGFwcHJvYWNoZXMgYmFzZWQgb24gdGhlIHR5cGUgb2YgdGhlIHJlc3BvbnNlIChZKSB2YXJpYWJsZQogICAgLSAqKlJlZ3Jlc3Npb24qKiBwcm9ibGVtcyBmcmVxdWVudGx5IGludm9sdmUgdG8gUXVhbnRpdGF0aXZlL0NvbnRpbnVvdXMgcmVzcG9uc2UKICAgIC0gKipDbGFzc2lmaWNhdGlvbioqIHByb2JsZW1zIGZyZXF1ZW50bHkgaW52b2x2ZSB0byBDYXRlZ29yaWNhbC9RdWFsaXRhdGl2ZSByZXNwb25zZQotIHRoZXJlIGFyZSBjZXJ0YWlubHkgZXhlcHRpb25zLi4uCiAgICAtIHNvbWUgbWV0aG9kcyBjYW4gYmUgcmVhc29uYWJseSBpbnRlcnByZXRlZCBpbiBib3RoIHdheXMKICAgIC0gc29tZSBtZXRob2RzIChlLmcuLCBLLW5lYXJlc3QgbmVpZ2hib3JzKSBjYW4gYmUgdXNlZCB3aXRoIGVpdGhlciBxdWFudGl0YXRpdmUgYW5kIGNhdGVnb3JpY2FsIHJlc3BvbnNlCgojIyBIZWFsdGggRXZhbHVhdGlvbiBhbmQgTGlua2FnZSB0byBQcmltYXJ5IENhcmUgU3R1ZHkKCioqUlE6IFdoYXQgcmlzayBmYWN0b3JzIGFyZSBhc3NvY2lhdGVkIHdpdGggc2VyaW91cyB0aG91Z2h0cyBvZiBzdWljaWRlPyoqCgoKIyMjIyBgSEVMUHN0dWR5YCBEYXRhCgotIFRoZSBIRUxQIHN0dWR5IHdhcyBhIHJhbmRvbWl6ZWQgY29udHJvbGxlZCBjbGluaWNhbCB0cmlhbCBmb3IgYWR1bHQgaW5wYXRpZW50cyB3aXRoIGEgaGlzdG9yeSBvZiBzdXNic3RhbmNlIGFidXNlLiAgUGFydGljaXBhbnRzIHdlcmUgcmVjcnVpdGVkIGZyb20gYSBkZXRveGlmaWNhdGlvbiB1bml0IGluIHRoZSBCb3N0b24gYXJlYS4gCi0gSW5jbHVzaW9uIGNyaXRlcmE6IAogICAgLSBhZHVsdHMsIAogICAgLSBTcGFuaXNoIG9yIEVuZ2xpc2ggbGFuZ3VhZ2UgcHJvZmljaWVuY3kKICAgIC0gcmVwb3J0ZWQgYWxjb2hvbCwgaGVyb2luLCBvciBjb2NhaW5lIGFzIHRoZWlyIGZpcnN0IG9yIHNlY29uZCBkcnVnIG9mIGNob2ljZQogICAgLSByZXNpZGVkIGluIHByb3hpbWl0eSB0byB0aGUgcHJpbWFyeSBjYXJlIGNsaW5pYyB0byB3aGljaCB0aGV5IHdvdWxkIGJlIHJlZmVycmVkIG9yIHdlcmUgaG9tZWxlc3MuIAotIEV4Y2x1c2lvbiBjcml0ZXJpYTogCiAgICAtIFBhdGllbnRzIHdpdGggZXN0YWJsaXNoZWQgcHJpbWFyeSBjYXJlIHJlbGF0aW9uc2hpcHMgdGhleSBwbGFubmVkIHRvIGNvbnRpbnVlCiAgICAtIHNpZ25pZmljYW50IGRlbWVudGlhCiAgICAtIHNwZWNpZmljIHBsYW5zIHRvIGxlYXZlIHRoZSBCb3N0b24gYXJlYSB0aGF0IHdvdWxkIHByZXZlbnQgcmVzZWFyY2ggcGFydGljaXBhdGlvbgogICAgLSBmYWlsdXJlIHRvIHByb3ZpZGUgY29udGFjdCBpbmZvcm1hdGlvbiBmb3IgdHJhY2tpbmcgcHVycG9zZXMKICAgIC0gcHJlZ25hbmN5Ci0gUHJvY2VkdXJlOiAKICAgIC0gUGF0aWVudHMgd2l0aCBubyBwcmltYXJ5IGNhcmUgcGh5c2ljaWFuIHdlcmUgcmFuZG9taXplZCB0byByZWNlaXZlIGEgbXVsdGlkaXNjaXBsaW5hcnkgYXNzZXNzbWVudCBhbmQgYSBicmllZiBtb3RpdmF0aW9uYWwgaW50ZXJ2ZW50aW9uIG9yIHVzdWFsIGNhcmUsIHdpdGggdGhlIGdvYWwgb2YgbGlua2luZyB0aGVtIHRvIHByaW1hcnkgbWVkaWNhbCBjYXJlLgogICAgLSBTdWJqZWN0cyB3ZXJlIGludGVydmlld2VkIGF0IGJhc2VsaW5lIGR1cmluZyB0aGVpciBkZXRveGlmaWNhdGlvbiBzdGF5CiAgICAtIGZvbGxvdy11cCBpbnRlcnZpZXdzIHdlcmUgdW5kZXJ0YWtlbiBldmVyeSA2IG1vbnRocyBmb3IgMiB5ZWFycy4gCiAgICAtIEEgdmFyaWV0eSBvZiBjb250aW51b3VzLCBjb3VudCwgZGlzY3JldGUsIGFuZCBzdXJ2aXZhbCB0aW1lIHByZWRpY3RvcnMgYW5kIG91dGNvbWVzIHdlcmUgY29sbGVjdGVkIGF0IGVhY2ggb2YgdGhlc2UgZml2ZSBvY2Nhc2lvbnMuCgojIyMjIFZhcmlhYmxlcyBvZiBpbnRlcmVzdAoKLSAqKmBzdWljaWRlYCAocmVzcG9uc2U7IHsibm8iLCAieWVzIn0pKio6IGV4cGVyaWVuY2VkIHNlcmlvdXMgdGhvdWdodHMgb2Ygc3VpY2lkZSBpbiBsYXN0IDMwIGRheXMgKG1lYXN1cmVkIGF0IGJhc2VsaW5lKQotIGBjZXNkYDogQ2VudGVyIGZvciBFcGlkZW1pb2xvZ2ljIFN0dWRpZXMgRGVwcmVzc2lvbiBtZWFzdXJlIGF0IGJhc2VsaW5lIChoaWdoIHNjb3JlcyBpbmRpY2F0ZSBtb3JlIGRlcHJlc3NpdmUgc3ltcHRvbXMpCi0gYHNleGA6IG1hbGUgb3IgZmVtYWxlCi0gYGF2Z0FsY29ob2xgOiBhdmVyYWdlIG51bWJlciBvZiBkcmlua3MgKHN0YW5kYXJkIHVuaXRzKSBjb25zdW1lZCBwZXIgZGF5LCBpbiB0aGUgcGFzdCAzMCBkYXlzIChtZWFzdXJlZCBhdCBiYXNlbGluZSkKLSBgcHNzX2ZyYDogcGVyY2VpdmVkIHNvY2lhbCBzdXBwb3J0IGJ5IGZyaWVuZHMgKG1lYXN1cmVkIGF0IGJhc2VsaW5lLCBoaWdoZXIgc2NvcmVzIGluZGljYXRlIG1vcmUgc3VwcG9ydCkKLSBgdHJlYXRgIHJhbmRvbWl6ZWQgdG8gSEVMUCBjbGluaWM6IG5vIHllcwoKCmBgYHtyfQpIRUxQc3R1ZHkgPC0gCiAgSEVMUHJjdCAlPiUKICBzZWxlY3Qoc3VpY2lkZSA9IGcxYiwgYWdlLCBjZXNkLCBzZXgsIGF2Z0FsY29ob2wgPSBpMSwgcHNzX2ZyKQoKIyBpbnNwZWN0IGRhdGEKZ2xpbXBzZShIRUxQc3R1ZHkpCmBgYAoKCgoKIyMgRGF0YSBQcmVwYXJhdGlvbgoKLSBUcmFpbmluZywgKHF1ZXJ5KSwgYW5kIHRlc3Qgc2V0cwotIFE6IFdoeSBwYXJ0aXRpb24gdGhlIGRhdGEgdGhpcyB3YXk/CiAgICAtIGV4cGxhaW4gaG93IHRoZSBjb2RlIGFjY29tcGxpc2hlcyB0aGlzCgoKYGBge3J9CgojIHNldCBSTkcgc2VlZCBmb3IgcmVwcm9kdWNpYmxlIHJlc3VsdHMKc2V0LnNlZWQoNTM4KSAKCiMgcGFydGl0aW9uIHRoZSBkYXRhCm4gPC0gbnJvdyhIRUxQc3R1ZHkpCnRlc3RfaWR4IDwtIHNhbXBsZS5pbnQobiwgc2l6ZSA9IHJvdW5kKDAuMjUgKiBuKSkgIyBzZWxlY3Qgcm93IG51bWJlcnMgZm9yIHRoZSB0ZXN0IHNldAp0cmFpbiA8LSBIRUxQc3R1ZHlbLXRlc3RfaWR4LCBdICAjIGV4Y2x1ZGUgdGhlIHRlc3Qgc2V0IGNhc2VzCm5yb3codHJhaW4pCgp0ZXN0IDwtIEhFTFBzdHVkeVt0ZXN0X2lkeCwgXSAgICAjIHRlc3Qgc2V0IGNhc2VzIG9ubHkKbnJvdyh0ZXN0KQpgYGAKCgoKIyMgVHJhaW5pbmcgJiBUZXN0IHNldHMKCi0gaWYgb3VyIGdvYWwgaXMgcHJlZGljdGlvbiBvciBpbmZlcmVuY2Ugd2UgbmVlZCB0byBiZSBkaXNjaXBsaW5lZAogICAgMS4gRWFjaCBvYnNlcnZhdGlvbiBjYW4gZWl0aGVyIGJlIHVzZWQgZm9yIGV4cGxvcmF0aW9uIG9yIGNvbmZpcm1hdGlvbiwgbm90IGJvdGguCiAgICAyLiBZb3UgY2FuIHVzZSBhIGNhc2UgYXMgb2Z0ZW4gYXMgeW91IGxpa2UgZm9yIGV4cGxvcmF0aW9uLCBidXQgKipvbmx5IG9uY2UqKiBmb3IgY29uZmlybWF0aW9uLiAKLSAqKkFzIHNvb24gYXMgeW91IHVzZSBhbiBvYnNlcnZhdGlvbiB0d2ljZSwgeW914oCZdmUgc3dpdGNoZWQgZnJvbSBjb25maXJtYXRpb24gdG8gZXhwbG9yYXRpb24uIE5PIENIRUFUSU5HLioqCiAgICAtIHdlJ2xsIG9ubHkgdXNlIHRoZSB0cmFpbmluZyBkYXRhIChgdHJhaW5gKSBmb3IgbW9kZWwgYnVpbGRpbmcKICAgIC0gd2Ugd2FudCB0byBwcmVzZXJ2ZSB0aGUgaW50ZWdyaXR5IG9mIHRoZSBgdGVzdGAgc2V0IGFzIGEgbWVhbnMgdG8gdmFsaWRhdGUgbW9kZWwgYWNjdXJhY3kKICAgIC0gd2UgZGlkbid0IHVzZSBhICJxdWVyeSIgc2V0IGhlcmUKLSB0aGUgKipyZWFsKiogdGVzdCBvZiB5b3VyIG1vZGVsIGlzIGl0J3Mgb3V0LW9mLXNhbXBsZSBwZXJmb3JtYW5jZQogICAgLSB0aGlzIGlzIHdoYXQgd2Ugd2FudCB0aGUgdGVzdCBzZXQgZm9yCiAgICAtIGlmIHlvdXIgb3V0IG9mIHNhbXBsZSBwZXJmb3JtYW5jZSBpcyAqKmJhZCoqIHlvdSBtaWdodCB3YW50IHRvIGZpeCBpdCBhbmQgdHJ5IGFnYWluLi4uIGJ1dCB5b3UncmUgc29ydCBvZiBzdHVjayAoc2VlICMyKQoKLSB0aGlzIGlzIHdoZXJlIGEgc2VwYXJhdGUgInF1ZXJ5IiBzZXQgcGFydGl0aW9uIGlzIGhhbmR5CiAgICAtIHByb3ZpZGVzIGEgcHJhY3RpY2UgZGF0YSBzZXQgZm9yIG91dCBvZiBzYW1wbGUgcGVyZm9ybWFuY2Ugd2l0aG91dCBqZW9wYXJkaXppbmcgdGhlIGludGVncml0eSBvZiB0aGUgdGVzdCBzZXQKICAgIC0gcGFydGljdWx1YXJseSB1c2VmdWwgZm9yIG1vZGVscyB0aGF0IGRlcGVuZCBvbiB1c2VyLXNwZWNpZmllZCAiaHlwZXJwYXJhbWV0ZXJzIiBsaWtlIHJlZ3VsYXJpemF0aW9uL3Nocmlua2FnZSAoY29taW5nIHVwIGxhdGVyKSBvciBCYXllc2lhbiBtZXRob2RzIAoKCiMjIEluc3BlY3RpbmcgdGhlIGBIRUxQc3R1ZHlgICh0cmFpbmluZykgZGF0YQoKLSB3ZSdyZSBjdXR0aW5nIEVEQSB0byB0aGUgYm9uZSB0byBiZSBlY29ub21pY2FsIHdpdGggbGVjdHVyZSB0aW1lICYgc2xpZGVzLCBidXQgeW91IG5lZWQgdG8gZG8gYSBjYXJlZnVsIEVEQSBvZiB5b3VyIGRhdGEgYmVmb3JlIHlvdSBzdGFydCBtb2RlbGluZy4gIAotIGNhcmVmdWwgRURBIGluIHRoZSBiZWdpbm5pbmcgd2lsbCBzYXZlIHlvdSBoZWFkYWNoZXMgJiB3YXN0ZWQgdGltZSBsYXRlcgotIHlvdSBzaG91bGQgYWxzbyB0byBwbG90IHlvdXIgZGF0YSBzZXZlcmFsIHdheXMgCiAgICAtIHRyeSBhbmQgY29tZSBhcyBjbG9zZSBhcyBwb3NzaWJsZSB0byBhbnN3ZXJpbmcgeW91ciByZXNlYXJjaCBxdWVzdGlvbiAKICAgIC0gdHJ5IGFuZCBleHBvc2UgaXNzdWVzIGluIHRoZSBkYXRhIHRoYXQgd2lsbCBpbXBhY3QgbW9kZWxpbmcgZGVjaXNpb25zCgoKYGBge3IgZmlnLmhlaWdodD0xMCwgZmlnLndpZHRoPTEwfQojIHNob3J0IChpbnN1ZmZpY2llbnQpIEVEQQp0YWxseSh+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbikKZmF2c3RhdHMofiBhZ2UsIGRhdGEgPSB0cmFpbikKZmF2c3RhdHMofiBjZXNkLCBkYXRhID0gdHJhaW4pCnRhbGx5KH4gc2V4LCBkYXRhID0gdHJhaW4pCmZhdnN0YXRzKH4gYXZnQWxjb2hvbCwgZGF0YSA9IHRyYWluKQpmYXZzdGF0cyh+IHBzc19mciwgZGF0YSA9IHRyYWluKQoKIyBzaW5nbGUgcGxvdDsgdWdseSwgYnV0IHBvc3NpYmx5IHVzZWZ1bCAoeW91IGNhbiBkbyBiZXR0ZXIpCnBhaXJzKHRyYWluKQpgYGAKCgojIyBOdWxsIG1vZGVsCgotIHRoaXMgZXN0YWJsaXNoZXMgYSB1c2VmdWwgYmFzZWxpbmUKLSB3aXRoIG5vIG90aGVyIGluZm9ybWF0aW9uIGF0IGFsbCwgd2Ugd291bGQgYmUgY29ycmVjdCBhYm91dCA3MiUgb2YgdGhlIHRpbWUgYnkganVzdCBhc3N1bWluZyB0aGF0IG5vbmUgb2YgdGhlc2UgcGVvcGxlIGV2ZXIgaGFkIHNlcmlvdXMgdGhvdWdodHMgb2Ygc3VpY2lkZS4KCmBgYHtyfQptb2RfbnVsbCA8LSB0YWxseSh+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbiwgZm9ybWF0ID0gInBlcmNlbnQiKQptb2RfbnVsbApgYGAKCgojIyBEZWNpc2lvbiBUcmVlcwoKLSAqKkNBUlQqKjogY2xhc3NpZmljYXRpb24gYW5kIHJlZ3Jlc3Npb24gdHJlZXMKLSB0cmVlLWxpa2UgZmxvdyBjaGFydCB0aGF0IGFzc2lnbnMgY2xhc3MgbGFiZWxzIHRvIGluZGl2aWR1YWwgb2JzZXJ2YXRpb25zCi0gbnVtYmVyIG9mIHBvc3NpYmxlIHRyZWVzIGdyb3dzIGV4cG9uZW50aWFsbHkgYXMgbnVtYmVyIG9mIFgncyBpbmNyZWFzZXMKLSB3ZSdsbCB1c2UgKipyZWN1cnNpdmUgcGFydGl0aW9uaW5nKiogdG8gcHJvZHVjZSBpbmNyZWFzaW5nbHkgInB1cmUiIHN1YnNldHMKCiFbY3JlZGl0OiA8aHR0cHM6Ly9uZXdvbmxpbmVjb3Vyc2VzLnNjaWVuY2UucHN1LmVkdS9zdGF0NTU1L25vZGUvMTAwLz5dKHJlY3Vyc2l2ZVBhcnRpdGlvbnMucG5nKQoKIyMgRGVjaXNpb24gdHJlZSAoc2ltcGxlKQoKLSBjb25zaWRlciBhIHNpbXBsZSB0cmVlIHRoYXQgcHJlZGljdHMgYHN1aWNpZGVgIGZyb20ganVzdCBgY2VzZGAgKGEgZGVwcmVzc2lvbiBzY29yZSkKLSB0aGUgdHJlZSBzaG93cyBzdWNjZXNzaXZlIHBhcnRpdGlvbmluZyB0byBwcm9kdWNlIGluY3JlYXNpbmdseSBwdXJlIHN1YnNldHMKCmBgYHtyfQpyZXF1aXJlKHJwYXJ0KQpycGFydChzdWljaWRlIH4gY2VzZCwgZGF0YSA9IHRyYWluKQpgYGAKCiMjIyMgdmlzdWFsaXplIGZpcnN0IHNwbGl0IGZvciBkZXByZXNzaW9uICYgc3VpY2lkZSBpZGVhdGlvbiBtb2RlbAoKLSBjbGVhcmx5IG5vdCBwZXJmZWN0Li4uCiAgICAtIGRlcHJlc3Npb24gc2NvcmVzIGxvd2VyIHRoYW4gdGhlIHNwbGl0IGFyZSBtb3JlIGNvbmZpZGVudGx5IGNsYXNzaWZpZWQgYXMgIm5vIgogICAgLSBhYm92ZSB0aGUgc3BsaXQgaXMgc3RpbGwgdmVyeSBoYXJkIHRvIHRlbGwKICAgIC0gUTogU28sIGlzIHRoaXMgc2luZ2xlIGN1dCBzY29yZSAqKnVzZWZ1bCoqPwoKYGBge3J9CnNwbGl0IDwtIDM0LjUgIyBmaXJzdCBzcGxpdCBmcm9tIHNpbXBsZSBgcnBhcnRgCnRyYWluICU+JQogIG11dGF0ZShlbGV2YXRlZF9kZXByZXNzaW9uID0gY2VzZCA+PSBzcGxpdCkgJT4lCiAgZ2dwbG90KGFlcyh4ID0gY2VzZCwgeSA9IHN1aWNpZGUpKSArIAogIGdlb21fcG9pbnQoYWVzKGNvbG9yID0gZWxldmF0ZWRfZGVwcmVzc2lvbiksIAogICAgICAgICAgICAgcG9zaXRpb24gPSBwb3NpdGlvbl9qaXR0ZXIod2lkdGggPSAwLCBoZWlnaHQgPSAwLjE1KSwgCiAgICAgICAgICAgICBhbHBoYSA9IDAuNCkgKyAKICBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQgPSBzcGxpdCwgY29sb3IgPSAiYmx1ZSIsIGx0eSA9IDIpCmBgYAoKIyMgRGVjaXNpb24gdHJlZSAoY29tcGxldGUpCgotIHdlJ3JlIGdvaW5nIHRvIHJldXNlIHRoZSBtb2RlbCBmb3JtdWxhIGEgbG90LCBzbyBNRFNSIHN0b3JlcyB0aGUgZm9ybXVsYSBgZm9ybWAKICAgIC0gYGZvcm0gPC0gYXMuZm9ybXVsYSgic3VpY2lkZSB+IGFnZSArIGNlc2QgKyBzZXggKyBhdmdBbGNvaG9sICsgcHNzX2ZyIilgCiAgICAtIHRoaXMgaXMgaWRlbnRpY2FsIHRvIGBzdWljaWRlIH4gLiBgIHNpbmNlIHdlJ3JlIHVzaW5nIGFsbCB0aGUgdmFyaWFibGVzIGluIGB0cmFpbmAKCgpgYGB7cn0KbW9kX3RyZWUgPC0gcnBhcnQoc3VpY2lkZSB+IC4sIGRhdGEgPSB0cmFpbikKbW9kX3RyZWUKYGBgCgojIyBEZWNpc2lvbiB0cmVlIChwYXJ0eWtpdCkKCmBgYHtyIGZpZy5oZWlnaHQ9MTAsIGZpZy53aWR0aD0xMH0KcmVxdWlyZShwYXJ0eWtpdCkKcGxvdChhcy5wYXJ0eShtb2RfdHJlZSkpCmBgYAoKPCEtLSBEYXkyIC0tPgoKIyMgQnJhbmNoaW5nIGFuZCBwcnVuaW5nIAoKLSB0aGUgYWxnb3JpdGhtIGNvbnNpZGVycyAqbWFueSogcG9zc2libGUgc3BsaXRzIChuZXcgYnJhbmNoZXMpLCBidXQgcHJ1bmVzIHRoZW0gaWYgdGhleSBkb24ndCBzdWZmaWNpZW50bHkgaW1wcm92ZSB0aGUgcHJlZGljdGl2ZSBwb3dlciBvZiB0aGUgbW9kZWwgKGkuZS4gYmVhciBmcnVpdCkgCi0gYSAqKmNvbXBsZXhpdHkgcGFyYW1ldGVyKiogaXMgdXNlZCB0byBjb250cm9sIHdoZXRoZXIgdG8ga2VlcCBvciBwcnVuZSBwb3NzaWJsZSBzcGxpdHMKLSBgcHJpbnRjcGAgcHJpbnRzIGEgdGFibGUgb2Ygb3B0aW1hbCBwcnVuaW5ncyBiYXNlZCBvbiB0aGUgY29tcGxleGl0eSBwYXJhbWV0ZXIKCmBgYHtyfQpwcmludGNwKG1vZF90cmVlKQpgYGAKCgojIyBNb2RlbCBhY2N1cmFjeTogQ29uZnVzaW9uIG1hdHJpeAoKYGBge3J9CnRyYWluX3RyZWUgPC0gCiAgdHJhaW4gJT4lCiAgbXV0YXRlKHN1aWNpZGVfZHRyZWUgPSBwcmVkaWN0KG1vZF90cmVlLCB0eXBlID0gImNsYXNzIikpCgpjb25mdXNpb24gPC0gdGFsbHkoc3VpY2lkZV9kdHJlZSB+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbl90cmVlLCBmb3JtYXQgPSAiY291bnQiKQpjb25mdXNpb24KCmBgYAoKLSBpdCdzIGltcG9ydGFudCB0byBzY3J1dGluaXplIHRoZSBvdXRjb21lcyBwcmVkaWN0ZWQgYnkgdGhlIG1vZGVsIGFnYWluc3Qgb3V0Y29tZXMgb2JzZXJ2ZWQgaW4gdGhlIGRhdGEKLSBpbiB0aGlzIHdheSwgdGhlIHJlc3BvbnNlIHZhcmlhYmxlICJzdXBlcnZpc2VzIiBvdXIgbW9kZWwKLSBjb25mdXNpb24gbWF0cml4IGlzIGEgc2ltcGxlLCBidXQgdXNlZnVsLCB0b29sIGZvciB0aGlzIHB1cnBvc2UKICAgIC0gZWFjaCB0eXBlIG9mIGNsYXNzaWZpY2F0aW9uIGFuZCBtaXNjbGFzc2lmaWNhdGlvbiBpcyByZXByZXNlbnRlZAogICAgLSBtb2RlbCAqKmFjY3VyYWN5Kio6IGNvcnJlY3QgLyB0b3RhbAogICAgLSBtb2RlbCAqKnNlbnNpdGl2aXR5KiogaXMgdGhlIHRydWUgcG9zaXRpdmUgcmF0ZQogICAgLSBtb2RlbCAqKnNwZWNpZmljaXR5KiogaXMgdGhlIHRydWUgbmVnYXRpdmUgcmF0ZQotIFE6IEhvdyBkbyB3ZSBrbm93IGlmIGl0J3MgYW55IGdvb2QgdGhvdWdoPwoKYGBge3J9CiMgZGVjaXNpb24gdHJlZSBtb2RlbCBhY2N1cmFjeQpkdHJlZV9hY2MgPC0gc3VtKGRpYWcoY29uZnVzaW9uKSkgLyBucm93KHRyYWluKSAqIDEwMApkdHJlZV9hY2MKYGBgCgoKIyMgQ2hhbmdpbmcgdGhlIGNvbnRyb2wgcGFyYW1ldGVyCgotIFE6IFdoYXQgZG8geW91IHRoaW5rIGhhcHBlbnMgaWYgd2UgY2hhbmdlIHRoZSBjb250cm9sIHBhcmFtZXRlcj8KICAgIC0gd2lsbCB0aGUgbW9kZWwgd2lsbCBiZSBtb3JlICYgbGVzcyBjb21wbGV4PwogICAgLSB3aGljaCBkbyB5b3UgdGhpbmsgdGhlIG1vZGVsIHdpbGwgYmUgbW9yZSAiYWNjdXJhdGUiPwoKYGBge3J9CiMgZGlmZmVyZW50IGNvbnRyb2wgcGFyYW1ldGVyIGZvciBjb21wYXJpc29uCm1vZF90cmVlMiA8LSBycGFydChzdWljaWRlIH4gLiwgZGF0YSA9IHRyYWluLCBjb250cm9sID0gcnBhcnQuY29udHJvbChjcCA9IDAuMDMpKQoKCnBsb3QoYXMucGFydHkobW9kX3RyZWUyKSkKCnRyYWluX3RyZWUyIDwtIAogIHRyYWluICU+JQogIG11dGF0ZShzdWljaWRlX2R0cmVlID0gcHJlZGljdChtb2RfdHJlZTIsIHR5cGUgPSAiY2xhc3MiKSkKCmNvbmZ1c2lvbiA8LSB0YWxseShzdWljaWRlX2R0cmVlIH4gc3VpY2lkZSwgZGF0YSA9IHRyYWluX3RyZWUyLCBmb3JtYXQgPSAiY291bnQiKQpjb25mdXNpb24KCnN1bShkaWFnKGNvbmZ1c2lvbikpIC8gbnJvdyh0cmFpbikgKiAxMDAKCgpgYGAKCiMjIE9wdGltYWwgZGVjaXNpb24gdHJlZQoKLSBIYXlhZmlsICYgUml2ZXN0ICgxOTc2KSBwcm92ZWQgdGhhdCBhbiBlZmZpY2llbnQgYWxnb3JpdGhtIHRvIGRldGVybWluZSB0aGUgb3B0aW1hbCBkZWNpc2lvbiB0cmVlIGFsbW9zdCBjZXJ0YWlubHkgZG9lcyBub3QgZXhpc3QgCiAgICAtIGRlY2lzaW9uIHRyZWUgb3B0aW1pemF0aW9uIGlzIE5QLWNvbXBsZXRlCiAgICAtIE5QOiByZXN1bHQgY2FuIGJlIGNoZWNrZWQgcXVpY2tseSB3aXRoIGFuIGFsZ29yaXRobSAoZS5nLiwgcG9seW5vbWlhbCB0aW1lKQogICAgLSBQOiBwcm9ibGVtcyB0aGF0IGNhbiBiZSBzb2x2ZWQgcXVpY2tseSB3aXRoIGFuIGFsZ29yaXRobSAoZS5nLiwgcG9seW5vbWlhbCB0aW1lKSAKICAgIC0gc29tZSBwcm9ibGVtcyBzZWVtIHRvIGJlIGVhc3kgdG8gY2hlY2sgKE5QKSBidXQgTk9UIG5lY2Vzc2FyaWx5IGVhc3kgdG8gc29sdmUgKFApLCBsaWtlIFN1ZG9rdSBwdXp6bGVzCiAgICAtIFAgdnMgTlA6IGFyZSBhbGwgcHJvYmxlbXMgaW4gTlAgYWxzbyBpbiBQPyAgCiAgICAtIG1vc3QgY29tcHV0ZXIgc2NpZW50aXN0cyBzdXNwZWN0ICRQIFxuZSBOUCQsIGJ1dCBpdCBoYXNuJ3QgYmVlbiBwcm92ZW4gKHlldCkKICAgIC0gdGhlcmUncyBhIGhhbmRzb21lIGJvdW50eSBpZiAqKmVpdGhlciB3YXkqKiBpcyBwcm92ZW4KICAgICAgICAtIE1pbGxlbml1bSBQcml6ZSBwcm9ibGVtcwogICAgICAgIC0gb25lIG9mIHNldmVuIG9wZW4gcHJvYmxlbXMgd2l0aCAkMSBtaWxsaW9uIChVUykgcmV3YXJkIGZvciBzb2x1dGlvbiEKICAgICAgICAtIG9uZSBwcml6ZSBoYXMgYWxyZWFkeSBiZWVuIGNsYWltZWQsIHNvIGFjdCBub3cgd2hpbGUgc3VwcGxpZXMgbGFzdCEKCi0gUTogQW55IGlkZWFzIGhvdyB3ZSBjYW4gaW1wcm92ZSByZXN1bHRzIGZvciBvdXIgdHJlZT8gCgoKIyMgRm9yZXN0cwoKLSBhIGZvcmVzdCBpcyBhIGNvbGxlY3Rpb24gb2YgdHJlZXNbY2l0YXRpb24gbmVlZGVkXS4KCiFbXShmb3Jlc3QucG5nKQoKIyMgUmFuZG9tIEZvcmVzdHMKCi0gYSByYW5kb20gZm9yZXN0IGlzIGEgY29sbGVjdGlvbiBvZiBkZWNpc2lvbiB0cmVlcy4KLSB3ZSBtb3JlIG9yIGxlc3MgYm9vdHN0cmFwIHRoZSBkZWNpc2lvbiB0cmVlcyBhbmQgZGVmZXIgdG8gdGhlIG1ham9yaXR5Ci0gcHJvY2VkdXJlOiAKICAgIDAuIGNob29zZSBudW1iZXIgb2YgdHJlZXMgdG8gImdyb3ciIChgbnRyZWVgIGFyZ3VtZW50KSBBTkQgdGhlIG51bWJlciBvZiB2YXJpYWJsZXMgdG8gY29uc2lkZXIgaW4gZWFjaCB0cmVlIChgbXRyeWAgYXJndW1lbnQpCiAgICAxLiBzYW1wbGUgdGhlIGNhc2VzIGluIHRoZSBkYXRhICoqd2l0aCByZXBsYWNlbWVudCoqCiAgICAyLiByYW5kb21seSBzZWxlY3QgYG10cnlgIG9mIHRoZSBleHBsYW5hdG9yeSB2YXJpYWJsZXMgYXQgZWFjaCBzcGxpdAogICAgMy4gYnVpbGQgKGdyb3c/KSBhIGRlY2lzaW9uIHRyZWUgb24gdGhlIHJlc3VsdGluZyBkYXRhCiAgICA0LiByZXBlYXQgYG50cmVlYCB0aW1lcwotIHRoaXMgYm9vdHN0cmFwIGFnZ3JlZ3JhdGlvbiBpcyBzb21ldGltZXMgY2FsbGVkICoqYmFnZ2luZyoqCi0gcHJlZGljdGlvbnMgYXJlIGJhc2VkIG9uIG1ham9yaXR5IHJ1bGUgZnJvbSBhbGwgdGhlIHRyZWVzIGluIHRoZSBmb3Jlc3QKICAgIC0gYG50cmVlYCBzaG91bGRuJ3QgYmUgdG9vIHNtYWxsLi4uIGJ1dCBjYW4gYmUgY29tcHV0YXRpb25hbGx5IGludGVuc2l2ZQogICAgLSBgbXRyeWAgZGVmYXVsdHMgdG8gJFxzcXJ0e3B9JCBmb3IgY2xhc3NpZmljYXRpb24gdHJlZXMgYW5kICRwIC8gMyQgZm9yIHJlZ3Jlc3Npb24gdHJlZXMKCmBgYHtyfQpyZXF1aXJlKHJhbmRvbUZvcmVzdCkKCm1vZF9mb3Jlc3QgPC0gcmFuZG9tRm9yZXN0KHN1aWNpZGUgfiAuLCBkYXRhID0gdHJhaW4sIG50cmVlID0gMjAwMCwgbXRyeSA9IDIpCm1vZF9mb3Jlc3QKCiMgbm90ZSB0aGUgYnVpbHQtaW4gY29uZnVzaW9uIG1hdHJpeApyZl9hY2MgPC0gc3VtKGRpYWcobW9kX2ZvcmVzdCRjb25mdXNpb24pKSAvIG5yb3codHJhaW4pICogMTAwCnJmX2FjYwoKYGBgCgojIyBCYWdnaW5nCgotICoqQmFnZ2luZyoqCiAgICAtIFByb2NlZHVyZTogCiAgICAgICAgLSBjcmVhdGUgbXVsdGlwbGUgY29waWVzIG9mIHRoZSBvcmlnaW5hbCB0cmFpbmluZyBkYXRhIHNldCB1c2luZyB0aGUgYm9vdHN0cmFwCiAgICAgICAgLSBmaXQgYSBzZXBhcmF0ZSBkZWNpc2lvbiB0cmVlIHRvIGVhY2ggY29weQogICAgICAgIC0gY29tYmluZSBhbGwgb2YgdGhlIHRyZWVzIGluIG9yZGVyIHRvIGNyZWF0ZSBhIHNpbmdsZSBwcmVkaWN0aXZlIG1vZGVsCiAgICAtIG9uIGF2ZXJhZ2UsIGVhY2ggYmFnZ2VkIHRyZWUgb25seSBtYWtlcyB1c2Ugb2YgYWJvdXQgMi8zIG9mIHRoZSB0cmFpbmluZyBkYXRhCiAgICAtIG91dC1vZi1iYWcgKE9PQikgZXJyb3IgaXMgbGlrZSBhIGZyZWUgcXVlcnkgc2V0IGJhc2VkIG9uIHByZWRpY3Rpb25zIG9mIHRoZSBzYW1wbGVzIE5PVCBjaG9zZW4gZm9yIGEgcGFydGljdWxhciB0cmVlCi0gc2VsZWN0aW5nIGEgcmFuZG9tIHN1YnNldCBvZiB0aGUgKip2YXJpYWJsZXMqKiBpcyBhbiBpbXByb3ZlbWVudCBvZiByYW5kb20gZm9yZXN0cyBvdmVyIGJhZ2dlZCB0cmVlcyBpbiBnZW5lcmFsIGluIG9yZGVyIHRvIGRlY29ycmVsYXRlIHRoZSB0cmVlcwoKCiMjIFJhbmRvbSBGb3Jlc3RzIChpbXBvcnRhbmNlKQoKLSAqKmltcG9ydGFuY2UqKiBpcyBhIG1ldHJpYyB1c2VmdWwgdG8gYXNzZXNzIHdoaWNoIHZhcmlhYmxlcyBhcmUgY29uc2lzdGVudGx5IGluZmx1ZW50aWFsCi0gbm90IGFzIGZvcm1hbCBhcyBhIHAtdmFsdWUgZm9yIHNpZ25pZmljYW5jZQogICAgLSBkZXByZXNzaW9uIHNjb3JlIChgY2VzZGApIGFwcGVhcnMgbW9zdCBpbXBvcnRhbnQKICAgIC0gYHNleGAgbGVhc3QgaW1wb3J0YW50CiAgICAtIG90aGVyIHZhcmlhYmxlcyBzb21ld2hlcmUgaW4gYmV0d2VlbgotIHRoZSAqKkdpbmkgY29lZmZpY2llbnQqKiBtZWFzdXJlcyB0aGUgcHVyaXR5IG9mIGEgc2V0IG9mIGNhbmRpZGF0ZSBjaGlsZCBub3RlcwoKYGBge3J9CnJlcXVpcmUodGliYmxlKQppbXBvcnRhbmNlKG1vZF9mb3Jlc3QpICU+JQogIGFzLmRhdGEuZnJhbWUoKSAlPiUKICByb3duYW1lc190b19jb2x1bW4oKSAlPiUgICMgaGFuZHkgZnVuY3Rpb24gZnJvbSBgdGliYmxlYCBwYWNrYWdlCiAgYXJyYW5nZShkZXNjKE1lYW5EZWNyZWFzZUdpbmkpKQpgYGAKCiMjIEJvb3N0aW5nCgotIEJvb3N0aW5nIHdvcmtzIHNpbWlsYXIgdG8gYmFnZ2luZywgZXhjZXB0IHRyZWVzIGFyZSBncm93biAqKnNlcXVlbnRpYWxseSoqOiBlYWNoIHRyZWUgaXMgZ3Jvd24gdXNpbmcgaW5mb3JtYXRpb24gZnJvbSBwcmV2aW91c2x5IGdyb3duIHRyZWVzLiAKLSBCb29zdGluZyBkb2VzIG5vdCBpbnZvbHZlIGJvb3RzdHJhcCBzYW1wbGluZzsgZWFjaCB0cmVlIGlzIGZpdCBvbiBhIG1vZGlmaWVkIHZlcnNpb24gb2YgdGhlIG9yaWdpbmFsIGRhdGEgc2V0Ci0gQm9vc3RpbmcgKmxlYXJucyBzbG93bHkqIGJ5IHByaW9yaXRpemluZyB0aGUgKipoYXJkKiogZXhhbXBsZXMgdGhhdCB3ZXJlIGZpdCBwb29ybHkgaW4gdGhlIHByZXZpb3VzIG1vZGVsCi0gQmVjYXVzZSB0aGUgZ3Jvd3RoIG9mIGEgcGFydGljdWxhciB0cmVlIHRha2VzIGludG8gYWNjb3VudCB0aGUgb3RoZXIgdHJlZXMgdGhhdCBoYXZlIGFscmVhZHkgYmVlbiBncm93biwgc21hbGxlcgp0cmVlcyBhcmUgdHlwaWNhbGx5IHN1ZmZpY2llbnQgYW5kIGFpZHMgaW4gaW50ZXJwcmV0YWJpbGl0eS4KCgpgYGB7cn0KcmVxdWlyZShnYm0pCgojIHJlc3BvbnNlIG11c3QgYmUgY29udmVydGVkIHRvIDAvMQp0cmFpbl9ib29zdCA8LSAKICB0cmFpbiAlPiUKICBtdXRhdGUoc3VpY2lkZTAxID0gaWZfZWxzZShzdWljaWRlID09ICJ5ZXMiLCAxLCAwKSkgJT4lCiAgc2VsZWN0KC1zdWljaWRlKQoKbW9kX2Jvb3N0IDwtIGdibShzdWljaWRlMDEgfiAuLCBkaXN0cmlidXRpb24gPSAiYmVybm91bGxpIiwgICAjIGJlY2F1c2UgaXQncyBhIGNsYXNzaWZpZXIgbW9kZWwKICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IHRyYWluX2Jvb3N0LCBuLnRyZWVzID0gMzAwMCwgaW50ZXJhY3Rpb24uZGVwdGggPSAyKSAKCiMgdGhlIHJlbGF0aXZlIGluZmx1ZW5jZSBpcyBzaW1pbGFyIHRvIGltcG9ydGFuY2UgcmVzdWx0IGVhcmxpZXIKbXN1bW1hcnkobW9kX2Jvb3N0KQoKYGBgCgoKCiMjIEstTmVhcmVzdCBOZWlnaGJvcgoKLSBzaW1wbGUgbWV0aG9kIHRoYXQgYXR0ZW1wdHMgdG8gcHJlZGljdCB3aXRob3V0IGNvbnN0cnVjdGluZyBhICJtb2RlbCIgCi0gcHJvY2VkdXJlOiAKICAgIC0gY2FsY3VsYXRlIHRoZSAqKmRpc3RhbmNlKiogYmV0d2VlbiBwYWlycyBvZiBwb2ludHMgaW4gdGhlICpwKi1kaW1lbnNpb25hbCBzcGFjZSAoZGVmaW5lZCBieSBvdXIgKnAqIGV4cGxhbmF0b3J5IHZhcmlhYmxlcykKICAgIC0gbmVhcmVzdCBuZWlnaGJvciBjbGFzc2lmaWVycyBzaW1wbHkgYXNzdW1lIHRoYXQgb2JzZXJ2YXRpb25zIHRoYXQgYXJlICJjbG9zZSIgdG8gb25lIGFub3RoZXIgcHJvYmFibHkgaGF2ZSBzaW1pbGFyIG91dGNvbWVzIChjbGFzcyBtZW1iZXJzaGlwKS4KLSB3ZSdsbCB1c2UgRXVjbGlkZWFuIGRpc3RhbmNlLCBidXQgdGhpcyBtZWFucyB3ZSBjYW4gb25seSB1c2UgcXVhbnRpdGF0aXZlIHZhcmlhYmxlcyAod2UgaGF2ZSB0byBkcm9wIGBzZXhgKQoKCiFbaW1hZ2UgY3JlZGl0OiBKYW1lcyBldCBhbCAoMjAxMykgPGh0dHA6Ly93d3ctYmNmLnVzYy5lZHUvfmdhcmV0aC9JU0wvPl0oa25uLnBuZykKCiMjIEtOTiBjbGFzc2lmaWVyCgotIEtOTiBjbGFzc2lmaWVycyBkb24ndCBuZWVkIHRvIHByb2Nlc3MgdGhlIHRyYWluaW5nIGRhdGEgZmlyc3QsIGl0IGNhbiBoYXBwZW4gb24gdGhlIGZseQogICAgLSB0aGV5J3JlIGZhc3QgJiBlYXN5IHRvIHVuZGVyc3RhbmQKICAgIC0gY2FuIGJlIGFkdmVyc2VseSBpbXBhY3RlZCBpZiBhIHdpZGVyIHNjYWxlIG9mIG9uZSB2YXJpYWJsZSBkd2FyZnMgYSBuYXJyb3cgc2NhbGUgb2YgYW5vdGhlciB2YXJpYWJsZSBpbiB0aGUgZGlzdGFuY2UgY2FsY3VsYXRpb24KLSB3ZSdsbCByZXN0cmljdCB0byB0aGUgdHJhaW5pbmcgZGF0YSAob25seSkgYmVjYXVzZSB3ZSBzdGlsbCBkb24ndCB3YW50IHRvIGxvb2sgYXQgdGhlIHRlc3Qgc2V0IHlldAotIG5vdGU6IGBjbCA9IHRyYWluJHN1aWNpZGVgIGFzIHRoZSBzdXBlcnZpc2luZyB2YXJpYWJsZSAoZnJvbSBgdHJhaW5gLCBub3QgYHRyYWluX3F1YW50YCkKCmBgYHtyfQpyZXF1aXJlKGNsYXNzKQp0cmFpbl9xdWFudCA8LSAKICB0cmFpbiAlPiUKICBzZWxlY3QoYWdlLCBjZXNkLCBhdmdBbGNvaG9sLCBwc3NfZnIpCgojIEtOTiBjbGFzc2lmaWVyCnN1aWNpZGVfa25uIDwtIGtubih0cmFpbiA9IHRyYWluX3F1YW50LCB0ZXN0ID0gdHJhaW5fcXVhbnQsIGNsID0gdHJhaW4kc3VpY2lkZSwgayA9IDUpCgojIGNvbmZ1c2lvbiBtYXRyaXgKY29uZnVzaW9uIDwtIHRhbGx5KHN1aWNpZGVfa25uIH4gc3VpY2lkZSwgZGF0YSA9IHRyYWluLCBmb3JtYXQgPSAiY291bnQiKQpjb25mdXNpb24KCmtubl9hY2MgPC0gc3VtKGRpYWcoY29uZnVzaW9uKSkgLyBucm93KHRyYWluKSAqIDEwMAprbm5fYWNjCmBgYAoKCiMjIEhvdyAobm90KSB0byBjaG9vc2Ugaz8KCi0gUTogd2hhdCdzIHdyb25nIHdpdGggdGhpcyBwaWN0dXJlPwogICAgLSB3aGljaCB2YWx1ZSBvZiAiayIgaGFzIHRoZSBiZXN0IHBlcmZvcm1hbmNlPwoKYGBge3J9Cmtubl9lcnJvcl9yYXRlIDwtIGZ1bmN0aW9uKHgsIHksIG51bU5laWdoYm9ycywgeiA9IHgpIHsKICAjIHB1cnBvc2U6IGZpdCBrbm4gY2xhc3NpZmllciBhbmQgcmV0dXJuIHByb3BvcnRpb24gb2YgbWlzY2xhc3NpZmljYXRpb25zCiAgIyBpbnB1dHM6IAogICMjIyB4OiB0cmFpbmluZyBkYXRhCiAgIyMjIHk6IHRydWUgY2xhc3NpZmNhdGlvbnMgZnJvbSBkYXRhCiAgIyMjIG51bU5laWdoYm9yczogbnVtYmVyIG9mIG5lYXJlc3QgbmVpZ2hib3JzIGZvciBjbGFzc2lmaWVyCiAgIyMjIHo6IHRlc3QgZGF0YSAoZGVmYXVsdCB0byB0cmFpbmluZyBkYXRhKQogIHlfaGF0IDwtIGtubih0cmFpbiA9IHgsIHRlc3QgPSB6LCBjbCA9IHksIGsgPSBudW1OZWlnaGJvcnMpCiAgcmV0dXJuKHN1bSh5X2hhdCAhPSB5KSAvIG5yb3coeCkpCn0KCmtzIDwtIGMoMToxNSwgMjAsIDI1LCAzMCwgNDAsIDUwKQp0cmFpbl9yYXRlcyA8LSBzYXBwbHkoa3MsIEZVTiA9IGtubl9lcnJvcl9yYXRlLCB4ID0gdHJhaW5fcXVhbnQsIHkgPSB0cmFpbiRzdWljaWRlKQprbm5fZXJyb3JfcmF0ZXMgPC0gZGF0YS5mcmFtZShrID0ga3MsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0cmFpbl9yYXRlID0gdHJhaW5fcmF0ZXMpCgprbm5fZXJyb3JfcmF0ZXMgJT4lCiAgZ2dwbG90KGFlcyh4ID0gaywgeSA9IHRyYWluX3JhdGUpKSArIAogIGdlb21fcG9pbnQoKSArIAogIGdlb21fbGluZSgpICsgCiAgeWxhYigiTWlzY2xhc3NpZmljYXRpb24gUmF0ZSIpCmBgYAoKCiMjIGNob2ljZSBvZiBrCgotIFE6IGhvdyB3b3VsZCB5b3UgY2hhcmFjdGVyaXplIHBlcmZvcm1hbmNlIG9mIGVhY2ggbW9kZWw/CiAgICAtIHdlIGhhdmUgdHdvIHF1YW50aXRhdGl2ZSB2YXJpYWJsZXMgYW5kIGEgYmluYXJ5IHJlc3BvbnNlIChvcmFuZ2U7IGJsdWUpCiAgICAtIHRoZSBkYXNoZWQgbGluZSBpcyBvcHRpbWFsCiAgICAtIHRoZSB0cmFpbmluZyBkYXRhIHBsb3R0ZWQKICAgIC0gbGVmdCBzaWRlIHNob3dzIEsgPSAxOyByaWdodCBzaWRlIEsgPSAxMDAKICAgIC0gY29sb3Igc2hvd3MgcHJlZGljdGlvbnMgZm9yIGVhY2ggS05OIGNsYXNzaWZpZXIgaW4gdGhlIGRhdGEgc3BhY2UgCgohW2ltYWdlIGNyZWRpdDogSmFtZXMgZXQgYWwgKDIwMTMpIDxodHRwOi8vd3d3LWJjZi51c2MuZWR1L35nYXJldGgvSVNMLz5dKGtubjIucG5nKQoKPCEtLSBEYXkzIC0tPgoKIyMgTmFpdmUgQmF5ZXMKCi0gYWxpYXNlcwogICAgLSBpbmRlcGVuZGVuY2UgQmF5ZXMKICAgIC0gc2ltcGxlIEJheWVzCi0gTmFpdmU/CiAgICAtIGR1ZSB0byBwb3NzaWJseSBzaW1wbGlzdGljIGFzc3VtcHRpb24gdGhhdCBleHBsYW5hdG9yeSB2YXJpYWJsZXMgYXJlIGNvbmRpdGlvbmFsbHkgaW5kZXBlbmRlbnQKICAgIC0gKipjb25kaXRpb25hbCBpbmRlcGVuZGVuY2UqKjogJFhfMSQgYW5kICRYXzIkIGFyZSBjb25kaXRpb25hbGx5IGluZGVwZW5kZW50IGdpdmVuICRZJCBpZiwgJFAoWF8xIHwgWF8yIFkpID0gUChFXzEgfCBZKSQgb3IgZXF1aXZhbGVudGx5ICRQKFhfMSBYXzIgfCBZKSA9IFAoWF8xIHwgWSkgUChYXzIgfCBZKSQKICAgIC0gY29uZGl0aW9uYWwgaW5kZXBlbmRlbmNlIG1lYW5zIHRoZSB0d28gZXhwbGFuYXRvcnkgdmFyaWFibGVzIGFyZSBpbmRlcGVuZGVudCBnaXZlbiBrbm93bGVkZ2Ugb2YgJFkkLCBidXQgdGhpcyBkb2Vzbid0IG5lY2Vzc2FyaWx5IG1lYW4gdGhleSBhcmUgaW5kZXBlbmRlbnQgb2Ygb25lIGFub3RoZXIgKG9yIHVuY29ycmVsYXRlZCkKICAgIC0gc2VlIFNUQVQgMzE4LzQxNCBmb3IgbW9yZSBvbiBjb25kaXRpb25hbCBpbmRlcGVuZGVuY2UKCgojIyMjIEJheWVzIFRoZW9yZW06IAoKJCRcdGV4dHtQcn0oeXx4KSA9IFxmcmFje1x0ZXh0e1ByfSh4eSl9e1x0ZXh0e1ByfSh4KX0gPSBcZnJhY3tcdGV4dHtQcn0oeHx5KVx0ZXh0e1ByfSh5KX17XHRleHR7UHJ9KHgpfSQkCgojIyAqUCooYHN1aWNpZGVgID0gInllcyIgfCBgc2V4YCA9ICJtYWxlIikKCiQkXHRleHR7UHJ9KHl8eCkgPSBcZnJhY3tcdGV4dHtQcn0oeHkpfXtcdGV4dHtQcn0oeCl9ID0gXGZyYWN7XHRleHR7UHJ9KHh8eSlcdGV4dHtQcn0oeSl9e1x0ZXh0e1ByfSh4KX0kJAoKLSBjb25zaWRlciB0aGUgZmlyc3QgcGVyc29uIGluIG91ciB0cmFpbmluZyBzZXQKLSBsZXQncyBjYWxjdWxhdGUgJFAoXHRleHR7c3VpY2lkZX0gfCBcdGV4dHttYWxlfSkkLCB0aGVuIAogICAgLSAkeSQgaXMgYHN1aWNpZGUgPT0gInllcyJgCiAgICAtICR4JCBpcyBgc2V4ID09ICJtYWxlImAKCmBgYHtyfQpoZWFkKHRyYWluLCAxKQp0YWxseShzZXggfiBzdWljaWRlLCBkYXRhID0gdHJhaW4sIG1hcmdpbnMgPSBUUlVFKQp0YWxseSggfiBzZXgsIGRhdGEgPSB0cmFpbiwgbWFyZ2lucyA9IFRSVUUpCnRhbGx5KCB+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbiwgbWFyZ2lucyA9IFRSVUUpCmBgYAoKIyMjIyAqUCooYHN1aWNpZGVgID0gInllcyIgfCBgc2V4YCA9ICJtYWxlIikKCiQkUChcdGV4dHtzdWljaWRlfSB8IFx0ZXh0e21hbGV9KSA9IFxmcmFje1AoXHRleHR7bWFsZX18XHRleHR7c3VpY2lkZX0pUChcdGV4dHtzdWljaWRlfSl9e1AoXHRleHR7bWFsZX0pfSA9IFxmcmFjeyg2MS85MykoOTMvMzQwKX17KDI1NS8zNDApfSA9IFxmcmFjezAuMTh9ezAuNzV9ID0gMC4yNCQkCgotIEZvciB0aG9zZSBpbiBIRUxQcmN0IHBvcHVsYXRpb24sIHRoZSBwcm9iYWJpbGl0eSBvZiBzZXJpb3VzIHRob3VnaHRzIG9mIHN1aWNpZGUgZ2l2ZW4gKG9ubHkpIHRoYXQgdGhlIHBlcnNvbiBpcyBtYWxlIGlzIDAuMjQgIAotIFRoaXMgb25seSBhbGxvd2VkIHVzIHRvIHRha2Ugb25lIHZhcmlhYmxlIChgc2V4YCkgaW50byBjb25zaWRlcmF0aW9uICAKLSBhIE5haXZlIEJheWVzIGNsYXNzaWZpZXIgZXh0ZW5kcyB0byBhZGRpdGlvbmFsIHZhcmlhYmxlcyBieSBhc3N1bWluZyBjb25kaXRpb25hbCBpbmRlcGVuZGVuY2UgIAoKCiMjIE5haXZlIEJheWVzIAoKLSBROiBIb3cgZGlkIHdlIGRvPwoKYGBge3J9CnJlcXVpcmUoZTEwNzEpICAjIGF3ZnVsIG5hbWUgZm9yIGEgcGFja2FnZS4uLgoKbW9kX25iIDwtIG5haXZlQmF5ZXMoc3VpY2lkZSB+IC4sIGRhdGEgPSB0cmFpbikKc3VpY2lkZV9uYiA8LSBwcmVkaWN0KG1vZF9uYiwgbmV3ZGF0YSA9IHRyYWluKQpjb25mdXNpb24gPC0gdGFsbHkoc3VpY2lkZV9uYiB+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbiwgZm9ybWF0ID0gImNvdW50IikKY29uZnVzaW9uCgpuYl9hY2MgPC0gc3VtKGRpYWcoY29uZnVzaW9uKSkgLyBucm93KHRyYWluKSAqIDEwMApuYl9hY2MKYGBgCgojIyBBcnRpZmljaWFsIE5ldXJhbCBOZXR3b3JrcwoKLSB1c2VmdWwgdG8gdGhpbmsgb2YgYSBuZXVyYWwgbmV0d29yayBhY2NvcmRpbmcgdG8gbGF5ZXJzIG9mIGluZm9ybWF0aW9uIHByb2Nlc3NpbmcKLSBldmVyeSBuZXVyYWwgbmV0d29yayBoYXMgb25lICoqaW5wdXQqKiBsYXllciB3aXRoIG5vZGVzIGNvcnJlc3BvbmRpbmcgdG8gZWFjaCBpbnB1dCB2YXJpYWJsZSAoaW5jbHVkaW5nIGluZGljYXRvcnMgZm9yIGZhY3RvcnMpCi0gZXZlcnkgbmV1cmFsIG5ldHdvcmsgaGFzIG9uZSAqKm91dHB1dCoqIGxheWVyIChvZnRlbiBvbmUgbm9kZSkKLSBhIG5ldXJhbCBuZXR3b3JrIGNhbiBoYXZlIG9uZSBvciBtb3JlICoqaGlkZGVuKiogbGF5ZXJzIHRoYXQgcmVjb25jaWxlIHBhdHRlcm5zIGZyb20gdGhlIGlucHV0cyB0aGF0IGNvcnJlc3BvbmQgdG8gb3V0cHV0cwogICAgLSBndWlkYW5jZSBhdmFpbGFibGUgb24gd2hlbiBhIG5ldXJhbCBuZXR3b3JrIGJlbmVmaXRzIGZyb20gbXVsdGlwbGUgaGlkZGVuIGxheWVycwogICAgLSBndWlkYW5jZSBhdmFpbGFibGUgb24gc2l6ZSBvZiBoaWRkZW4gbGF5ZXIocykKLSB0aGUgYWxnb3JpdGhtIGVzc2VudGlhbGx5IHNlYXJjaGVzIGZvciBhbiBvcHRpbWFsIHNldCBvZiB3ZWlnaHRzIGNvcnJlc3BvbmRpbmcgdG8gZWRnZXMgYmV0d2VlbiBhbGwgcGFpcnMgb2Ygbm9kZXMgaW4gc3VjY2Vzc2l2ZSBsYXllcnMgKGlucHV0ID4+IGhpZGRlbihzKSA+PiBvdXRwdXQpCgoKCmBgYHtyfQpyZXF1aXJlKG5uZXQpCm1vZF9ubmV0IDwtIG5uZXQoc3VpY2lkZSB+IC4sIGRhdGEgPSB0cmFpbiwgc2l6ZSA9IDgpCgpzdWljaWRlX25uIDwtIHByZWRpY3QobW9kX25uZXQsIG5ld2RhdGEgPSB0cmFpbiwgdHlwZSA9ICJjbGFzcyIpCgpjb25mdXNpb24gPC0gdGFsbHkoc3VpY2lkZV9ubiB+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbiwgZm9ybWF0ID0gImNvdW50IikKY29uZnVzaW9uCgpubmV0X2FjYyA8LSBzdW0oZGlhZyhjb25mdXNpb24pKSAvIG5yb3codHJhaW4pICogMTAwCm5uZXRfYWNjCmBgYAoKYGBge3J9CiMgUGxvdHRpbmcgYXJ0aWZpY2lhbCBuZXVyYWwgbmV0d29ya3MgKG5vIHBsb3R0aW5nIGZ1bmN0aW9uIGluIGBubmV0YCBwYWNrYWdlKQoKIyBpbXBvcnQgZnVuY3Rpb24gZnJvbSBHaXRodWIgCmxpYnJhcnkoZGV2dG9vbHMpCnNvdXJjZV91cmwoJ2h0dHBzOi8vZ2lzdC5naXRodWJ1c2VyY29udGVudC5jb20vZmF3ZGExMjMvNzQ3MTEzNy9yYXcvNDY2YzE0NzRkMGE1MDVmZjA0NDQxMjcwMzUxNmMzNGYxYTQ2ODRhNS9ubmV0X3Bsb3RfdXBkYXRlLnInKQoKIyBwbG90IEFOTgpwbG90Lm5uZXQobW9kX25uZXQpCgpgYGAKCgojIyBMb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsCgpgYGB7cn0KIyBsb2dpc3RpYwptb2RfbG9naXQgPC0gZ2xtKHN1aWNpZGUgfiAuLCBkYXRhID0gdHJhaW4sIGZhbWlseSA9ICJiaW5vbWlhbCIpCm1zdW1tYXJ5KG1vZF9sb2dpdCkKCnN1aWNpZGVfbG9naXRQcm9iIDwtIHByZWRpY3QobW9kX2xvZ2l0LCBuZXdkYXRhID0gdHJhaW4sIHR5cGUgPSAicmVzcG9uc2UiKQpzdWljaWRlX2xvZ2l0IDwtIGlmZWxzZShzdWljaWRlX2xvZ2l0UHJvYiA+IDAuNSwgeWVzID0gInllcyIsICJubyIpCgpjb25mdXNpb24gPC0gdGFsbHkoc3VpY2lkZV9sb2dpdCB+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbiwgZm9ybWF0ID0gImNvdW50IikKY29uZnVzaW9uCgpsb2dpdF9hY2MgPC0gc3VtKGRpYWcoY29uZnVzaW9uKSkgLyBucm93KHRyYWluKSAqIDEwMApsb2dpdF9hY2MKYGBgCgoKIyMgQXNpZGU6IFN1cHBvcnQgVmVjdG9yIE1hY2hpbmVzCgohW2ltYWdlIGNyZWRpdDogSmFtZXMgZXQgYWwgKDIwMTMpIDxodHRwOi8vd3d3LWJjZi51c2MuZWR1L35nYXJldGgvSVNMLz5dKG1heGltYWxNYXJnaW5DbGFzc2lmaWVyLnBuZykKCi0gKipTdXBwb3J0IHZlY3RvciBtYWNoaW5lcyoqIGFyZSBhbm90aGVyIGdyb3VwIG9mIGNsYXNzaWZpY2F0aW9uIG1vZGVscyB0aGF0IGF0dGVtcHQgdG8gZGVmaW5lIGEgbWF0aGVtYXRpY2FsIGJvdW5kYXJ5IGJldHdlZW4gdHdvIGNsYXNzZXMKICAgIC0gKiptYXhpbWFsIG1hcmdpbiBjbGFzc2lmaWVyKio6IGlmIHBvc3NpYmxlIHRvIGlkZW50aWZ5IGEgbGluZSwgb3IgcGxhbmUsIChvciBoeXBlcnBsYW5lKSB0aGF0IHBlcmZlY3RseSBzZXBhcmF0ZXMgdGhlIHR3byBjbGFzc2VzLi4uCiAgICAgICAgLSB3ZSBjaG9vc2UgdGhlIGJvdW5kYXJ5IHRoYXQgbWF4aW1pemVzIHNlcGFyYXRpb24gCiAgICAgICAgLSB0aGUgKGZldykgcG9pbnRzIHRoYXQgZGVmaW5lIHRoZSBib3VuZGFyeSBhcmUgdGhlIHNvLWNhbGxlZCAic3VwcG9ydCB2ZWN0b3JzIiwgb3RoZXIgcG9pbnRzIGRvbid0IGltcGFjdCBwb3NpdGlvbiBvZiB0aGUgYm91bmRhcnkKICAgICAgICAtIHZlcnkgc2Vuc2l0aXZlIHRvIGEgZmV3IGluZmx1ZW50aWFsIHBvaW50cwogICAgLSAqKnN1cHBvcnQgdmVjdG9yIGNsYXNzaWZpZXIqKjogZXh0ZW5zaW9uIG9mIE1NQyB0aGF0IHBlcm1pdHMgYSAic29mdCBtYXJnaW4iIAogICAgICAgIC0gc3RpbGwgYSBsaW5lL3BsYW5lL2h5cGVycGxhbmUsIGJ1dCBhIG1hcmdpbiBvZiAidG9sZXJhbmNlIiBpcyBwZXJtaXR0ZWQKICAgICAgICAtIGltcHJvdmVzIHJvYnVzdG5lc3MgdG8gaW5kaXZpZHVhbCBvYnNlcnZhdGlvbnMKICAgICAgICAtIHN1cHBvcnQgdmVjdG9ycyBhcmUgZGVmaW5lZCBieSBhbnkgb2JzZXJ2YXRpb25zIG9uIHRoZSB3cm9uZyBzaWRlIG9mIHRoZSBtYXJnaW4gZm9yIHRoZWlyIGNsYXNzICh0aG9zZSBiZXlvbmQgdGhlIG1hcmdpbiBzdGlsbCBkb24ndCBhZmZlY3QgU1ZDKQogICAgLSAqKnN1cHBvcnQgdmVjdG9yIG1hY2hpbmUqKjogZXh0ZW5zaW9uIG9mIFNWQyB0aGF0IHBlcm1pdHMgYSBub24tbGluZWFyIGRlY2lzaW9uIGJvdW5kYXJ5IG1ldGhvZHMKLSBBcyBhIHRlY2huaWNhbCBwb2ludCwgU1ZNcyB0ZW5kIHRvIGdpdmUgZmFpcmx5IHNpbWlsYXIgcmVzdWx0cyB0byBsb2dpc3RpYyByZWdyZXNzaW9uCiAgICAtIFdoZW4gY2xhc3NlcyBhcmUgd2VsbC1zZXBhcmF0ZWQsIFNWTSBtYXkgYmUgcHJlZmVycmVkCiAgICAtIFdpdGggbW9yZSBvdmVybGFwcGluZyByZWdpbWVzLCBsb2dpc3RpYyByZWdyZXNzaW9uIGlzIG9mdGVuIHByZWZlcnJlZAoKCmBgYHtyfQpyZXF1aXJlKGUxMDcxKSAgIyBhZ2FpbiwgYXdmdWwgbmFtZSBmb3IgYSBwYWNrYWdlLi4uCgojIG1vZF9zdm0gPSBzdm0oc3VpY2lkZSB+IC4sIGRhdGEgPSB0cmFpbiwga2VybmVsID0gImxpbmVhciIsIGNvc3QgPSAxMCwgc2NhbGUgPSBGQUxTRSkKbW9kX3N2bSA9IHN2bShzdWljaWRlIH4gLiwgZGF0YSA9IHRyYWluLCBrZXJuZWwgPSAicmFkaWFsIiwgY29zdCA9IDEwLCBzY2FsZSA9IEZBTFNFKQpwcmludChtb2Rfc3ZtKQoKc3VpY2lkZV9zdm0gPC0gcHJlZGljdChtb2Rfc3ZtLCBuZXdkYXRhID0gdHJhaW4pCmNvbmZ1c2lvbiA8LSB0YWxseShzdWljaWRlX3N2bSB+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbiwgZm9ybWF0ID0gImNvdW50IikKY29uZnVzaW9uCgpzdm1fYWNjIDwtIHN1bShkaWFnKGNvbmZ1c2lvbikpIC8gbnJvdyh0cmFpbikgKiAxMDAKc3ZtX2FjYwpgYGAKCgoKCiMjIEhvdyBoYXZlIHdlIGRvbmUgc28gZmFyPwoKLSBXZSBuZWVkIHNvbWUgd2F5IHRvIGNvbXBhcmUgYW5kIGV2YWx1YXRlIG1vZGVscyAod2UnbGwgZm9ybWFsaXplIHRoaXMgaW4gYSBtb21lbnQpCi0gUTogd2hpY2ggbW9kZWwgd291bGQgeW91IGNob29zZT8KLSBROiBob3cgZG8geW91IGtub3cgd2hpY2ggcmVzdWx0KHMpIHRvIHRydXN0PyAKCmBgYHtyfQojIHN1bW1hcnkgb2YgcmVzdWx0cwpNb2RlbENvbXBhcmlzb24gPC0gCiAgdHJpYmJsZSgKICB+bW9kZWwsIH5hY2N1cmFjeSwgCiAgIioqTlVMTCBNT0RFTCoqIiwgbW9kX251bGxbMV0sIAogICJkZWNpc2lvbiB0cmVlIiwgZHRyZWVfYWNjLCAKICAicmFuZG9tIGZvcmVzdCIsIHJmX2FjYywgCiAgImstbmVhcmVzdCBuZWlnaGJvcnMiLCBrbm5fYWNjLCAKICAibmFpdmUgQmF5ZXMiLCBuYl9hY2MsIAogICJuZXVyYWwgbmV0d29yayIsIG5uZXRfYWNjLCAKICAibG9naXN0aWMgcmVncmVzc2lvbiIsIGxvZ2l0X2FjYwopCk1vZGVsQ29tcGFyaXNvbiAlPiUKICBhcnJhbmdlKGRlc2MoYWNjdXJhY3kpKQpgYGAKCiMjIEVuc2VtYmxlIG1ldGhvZHMKCi0gd2UgaGF2ZSBzZXZlcmFsIHBvc3NpYmx5IGxlZ2l0aW1hdGUgbW9kZWxzIHRoYXQgdGFrZSBhIGRpZmZlcmVudCBhcHByb2FjaCB0byBvdXIgY2xhc3NpZmljYXRpb24gcHJvYmxlbQotIGlmIGVhY2ggbW9kZWwgaGFzIHRha2VuIGFuIGluZGVwZW5kZW50IGFwcHJvYWNoLCB0aGVyZSdzIGEgY2xlYXIgYmVuZWZpdCB0byBjb21iaW5pbmcgdGhlbQotIGUuZy4sIGlmICRcZXBzaWxvbl9pJCBpcyB0aGUgZXJyb3IgcmF0ZSBvZiBtb2RlbCAkaSQsIHRoZW4gdGhlIGNoYW5jZSB0aGF0IGFsbCA1IG1vZGVscyBtaXNjbGFzc2lmeSBhIGNhc2UgaXMgc21hbGxlciB0aGFuIHRoZSBlcnJvciByYXRlIGZvciBhbnkgaW5kaXZpZHVhbCBzaW5jZSAkXHByb2Rfe2k9MX1ee2t9XGVwc2lsb25faSQgYW5kICRcZXBzaWxvbl9pIDwgMSQgZm9yIGFueSAkaSQKICAgIC0gd2UgZXhjbHVkZSB0aGUgbnVsbCBtb2RlbCAmIHJlcGxhY2UgdGhlIGRlY2lzaW9uIHRyZWUgd2l0aCByYW5kb20gZm9yZXN0IG1vZGVsCiAgICAtIFE6IHdoYXQgZG8gd2UgYWNoaWV2ZSB3aXRoIGRpZmZlcmVudCB2YWx1ZXMgZm9yIGB2b3RlYD8KCgpgYGB7cn0Kdm90ZSA8LSAzCgpzdWljaWRlX2Vuc2VtYmxlIDwtIAogIGlmZWxzZSgoc3VpY2lkZV9rbm4gICA9PSAieWVzIikgKyAKICAgICAgICAgKHN1aWNpZGVfbm4gICAgPT0gInllcyIpICsgCiAgICAgICAgIChzdWljaWRlX25iICAgID09ICJ5ZXMiKSArIAogICAgICAgICAoc3VpY2lkZV9sb2dpdCA9PSAieWVzIikgKyAKICAgICAgICAgKG1vZF9mb3Jlc3QkcHJlZGljdGVkID09ICJ5ZXMiKSA+PSB2b3RlLCAKICAgICAgICAgInllcyIsICJubyIpCgpjb25mdXNpb24gPC0gdGFsbHkoc3VpY2lkZV9lbnNlbWJsZSB+IHN1aWNpZGUsIGRhdGEgPSB0cmFpbiwgZm9ybWF0ID0gImNvdW50IikKY29uZnVzaW9uCgoKZW5zX2FjYyA8LSBzdW0oZGlhZyhjb25mdXNpb24pKSAvIG5yb3codHJhaW4pICogMTAwCgojIHN1bW1hcnkgb2YgcmVzdWx0cwpNb2RlbENvbXBhcmlzb24gPC0gCiAgdHJpYmJsZSgKICB+bW9kZWwsIH5hY2N1cmFjeSwgCiAgIioqTlVMTCBNT0RFTCoqIiwgbW9kX251bGxbMV0sIAogICJyYW5kb20gZm9yZXN0IiwgcmZfYWNjLCAKICAiay1uZWFyZXN0IG5laWdoYm9ycyIsIGtubl9hY2MsIAogICJuYWl2ZSBCYXllcyIsIG5iX2FjYywgCiAgIm5ldXJhbCBuZXR3b3JrIiwgbm5ldF9hY2MsIAogICJsb2dpc3RpYyByZWdyZXNzaW9uIiwgbG9naXRfYWNjLCAKICAiKipFTlNFTUJMRSoqIiwgZW5zX2FjYwopCk1vZGVsQ29tcGFyaXNvbiAlPiUKICBhcnJhbmdlKGRlc2MoYWNjdXJhY3kpKQpgYGAKCgoKIyMgRW5zZW1ibGUgTW9kZWxzCgotIEVuc2VtYmxlIG1ldGhvZHMgYXJlIGEgdXNlZnVsIHdheSB0byBoZWRnZSBvdXIgYmV0cwogICAgLSByZWNhbGw6IFJhbmRvbSBGb3Jlc3QgaXRzZWxmIGlzIGFuIGVuc2VtYmxpbmcgb2YgZGVjaXNpb24gdHJlZXMKICAgIC0gVGhlcmUgYXJlIG9mdGVuIGxvdHMgb2YgcmVhc29uYWJsZSBhcHByb2FjaGVzIHRvIG1vZGVsaW5nIGEgZ2l2ZW4gZGF0YSBzZXQKICAgIC0gR29vZCBvcHRpb24gZm9yIGJsZW5kaW5nIHNldmVyYWwgbW9kZWxzIG9yIHRoZSBzYW1lIG1vZGVsIHdpdGggZGlmZmVyZW50IHNldHRpbmdzCiAgICAtIEVzcGVjaWFsbHkgdXNlZnVsIHdoZW4gbW9kZWxzIGRpc2FncmVlICgqKlE6IFdoeT8qKikKLSBXZSBhbGxvd2VkIGVhY2ggbW9kZWwgdG8gaGF2ZSBhbiBlcXVhbCAidm90ZSIsIGJ1dCBhIHdlaWdodGVkIGVuc2VtYmxlIGlzIGEgc3RyYWlnaHQtZm9yd2FyZCBleHRlbnNpb24KLSBgU3VwZXJMZWFybmVyYCBwYWNrYWdlIGhhcyBzb21lIG5pY2UgdG9vbHMgdG8gZG8gdGhpcyBkaXJlY3RseQogICAgLSBpbmNsdWRlcyBsb3RzIG9mIHByZWRpY3RpdmUgbW9kZWxzIGZvciBjbGFzc2lmaWNhdGlvbiAmIHJlZ3Jlc3Npb24KICAgIC0gYWxzbyBpbmNsdWRlcyBzY3JlZW5pbmcgbW9kZWxzIGZvciB2YXJpYWJsZSBzZWxlY3Rpb24KICAgIC0gKippbXBvcnRhbnQqKiBgU3VwZXJMZWFybmVyYCBjYWxscyBvdGhlciBwYWNrYWdlcyBjb3JyZXNwb25kaW5nIHRvIHRoZSBhdmFpbGFibGUgbWV0aG9kcywgYW5kIHlvdSBuZWVkIHRvIGluc3RhbGwgeW91ciBvd24gcGFja2FnZSBkZXBlbmRlbmNpZXMgdG8gYWNjZXNzIHRob3NlIG1ldGhvZHMKCgpgYGB7cn0KcmVxdWlyZShTdXBlckxlYXJuZXIpCmxpc3RXcmFwcGVycygpICAjIGxpc3QgYXZhaWxhYmxlIG1vZGVscyBpbiBgU3VwZXJMZWFybmVyYAoKYGBgCgoKPCEtLSBEYXk0IC0tPgoKCiMjIE1vZGVsIEV2YWx1YXRpb24KCiFbaW1hZ2UgY3JlZGl0OiBKYW1lcyBldCBhbCAoMjAxMykgPGh0dHA6Ly93d3ctYmNmLnVzYy5lZHUvfmdhcmV0aC9JU0wvPl0oYmlhc1ZhcmlhbmNlLnBuZykKCgoKLSBXZSBoYXZlICoqb3ZlcmZpdCoqIHRoZSBkYXRhIGlmIHdlIGFsbG93IG91ciBtb2RlbCB0b28gbXVjaCBmbGV4aWJpbGl0eSB0byBhY2NvbW1vZGF0ZSB0aGUgaWRpb3N5bmNyYXNpZXMgb2YgdGhlIHRyYWluaW5nIGRhdGEuCi0gSXQncyBhbiBlYXN5IHRyYXAgdG8gc3R1bWJsZSBpbnRvLCBlc3BlY2lhbGx5IGlmIHdlIGZhaWwgdG8gcHJlc2VydmUgYSB0ZXN0IHNhbXBsZSBkdXJpbmcgbW9kZWxpbmcuCi0gQW4gb3ZlcmZpdHRlZCBtb2RlbCB3aWxsIHBlcmZvcm0gcG9vcmx5IHdoZW4gYXR0ZW1wdGluZyB0byBwcmVkaWN0IHJlc3VsdHMgZm9yIG5ldyAoaS5lLiB0ZXN0KSBkYXRhIHRoYXQgdGhlIG1vZGVsIGhhcyBuZXZlciBzZWVuIGJlZm9yZS4KLSBhIGZldyBwcmluY2lwbGVzIGZvciBldmFsdWF0aW5nIG1vZGVscwogICAgLSAqKmNyb3NzLXZhbGlkYXRpb24qKgogICAgLSAqKm1lYXN1cmluZyBwcmVkaWN0aW9uIGVycm9yKioKICAgIC0gKipDb25mdXNpb24gbWF0cmljZXMqKiAoYXMgd2UndmUgZGlzY3Vzc2VkKQogICAgLSAqKnJlY2VpdmVyIG9wZXJhdGluZyBjaGFyYWN0ZXJpc3RpYyAoUk9DKSBjdXJ2ZXMqKgogICAgLSAqKmJpYXMtdmFyaWFuY2UgdHJhZGVvZmYqKgotIExhc3RseSwgd2UnbGwgYWxzbyBtZW50aW9uICoqcmVndWxhcml6YXRpb24qKiBhcyBhIHN0cmF0ZWd5IHRvIHByb3RlY3QgYWdhaW5zdCBvdmVyZml0dGluZyBpbiByZWdyZXNzaW9uIG1vZGVsaW5nCgojIyBDcm9zcy12YWxpZGF0aW9uCgotIHdlIGhhZCBwYXJ0aXRpb25lZCBvdXIgdHJhaW5pbmcgYW5kIHRlc3QgZGF0YSBmcm9tIHRoZSBiZWdpbm5pbmcKLSBvbmNlIHdlIGFyZSBzYXRpc2ZpZWQgd2l0aCBvdXIgbW9kZWwsIHdlIHVzZSB0aGUgdGVzdCBzZXQgdG8gY2hhbGxlbmdlIG91ciBtb2RlbCB0byBwcmVkaWN0IHJlc3VsdHMgZm9yIG9ic2VydmF0aW9ucyBpdCBoYXMgbm90IHByZXZpb3VzbHkgZW5jb3VudGVyZWQKLSBXZSBjYWxsIHRoaXMgIm91dC1vZi1zYW1wbGUiIHRlc3RpbmcKLSBQb29yIHBlcmZvcm1hbmNlIHdvdWxkIHN1Z2dlc3QgdGhhdCBvdXIgbW9kZWwgaGFzIG92ZXJmaXQgdGhlIGRhdGEKLSBwcmVzZXJ2aW5nIGEgdGVzdCBzZXQgZnJvbSB0aGUgYmVnaW5uaW5nIGlzIGEgbW9yZSBwdXJlIGFwcHJvYWNoLCBidXQgY29tcHJvbWlzZXMgYXJlIGNvbW1vbgogICAgLSAqKjUwLTUwIGNyb3NzLXZhbGlkYXRpb24qKjogCiAgICAgICAgLSBTcGxpdCBkYXRhIGluIGhhbGYsIAogICAgICAgIC0gVXNlIHRoZSBmaXJzdCBoYWxmIHRvIHByZWRpY3QgdGhlIHNlY29uZCwgYW5kIHZpY2UgdmVyc2EuICAKICAgICAgICAtIEV2YWx1YXRlIHBlcmZvcm1hbmNlLiAgKGEuay5hLiAyLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbikKICAgIC0gKiprLWZvbGQgY3Jvc3MgdmFsaWRhdGlvbioqIChzZWUgYGNhcmV0YCBwYWNrYWdlKTogCiAgICAgICAgLSBTcGxpdCBkYXRhIGludG8gayBlcXVhbCBwYXJ0aXRpb25zLiAgCiAgICAgICAgLSBVc2UgKiplYWNoKiogb2YgdGhlIGsgcGFydGl0aW9ucyBpbiB0dXJuIGFzIHRoZSAidGVzdCIgc2V0IHdoaWxlIG90aGVyICQoayAtIDEpJCBwYXJ0aXRpb25zIGFyZSBwb29sZWQgZm9yIHVzZSBhcyB0cmFpbmluZyBzZXQuCiAgICAgICAgLSBBZ2dyZWdhdGUgdGhlIHJlc3VsdHMgZm9yIGFsbCBvZiB0aGUgayBwYXJ0aXRpb25zCgoKIyMgUHJlZGljdGlvbiBlcnJvcgoKLSBmb3IgcXVhbnRpdGF0aXZlIHJlc3BvbnNlcywgd2UgaGF2ZSBzZXZlcmFsIGNvbW1vbiBtZXRyaWNzIGZvciBhc3Nlc3NpbmcgcHJlZGljdGl2ZSBwZXJmb3JtYW5jZQogICAgLSBjb21tb25seSB1c2VkIGV2ZW4gd2hlbiB0ZXN0IHNldCBpcyBub3QgYXZhaWxhYmxlIChlLmcsIGxlYXZlLW9uZS1vdXQpCiAgICAtIHdoZW4gYXBwbHlpbmcgdG8gdGVzdCBzZXQKLSBFdmFsdWF0ZSBkZXZpYXRpb25zIGJldHdlZW4gb2JzZXJ2ZWQgYW5kIHByZWRpY3RlZCB2YWx1ZXMKICAgIC0gUk1TRTogJFxzcXJ0e1xmcmFjezF9e259XHN1bSh5IC0gXGhhdHt5fSleMn0kCiAgICAtIE1BRTogJFxmcmFjezF9e259XHN1bXx5IC0gXGhhdHt5fXwkCi0gQ29ycmVsYXRpb246IHVuaXRsZXNzIHNjYWxlICgtMSwgMSkgd2l0aCBubyBjb3JyZWxhdGlvbiBuZWFyIHplcm8sIHN0cm9uZyBwb3NpdGl2ZSBjb3JyZWxhdGlvbiBuZWFyIDEgKGFuZCBzdHJvbmcgbmVnYXRpdmUgbmVhciAtMSkKICAgIC0gKG1vc3QgZmFtaWxpYXIpIFBlcnNvbidzIHByb2R1Y3QtbW9tZW50IGNvcnJlbGF0aW9uIAogICAgLSAocmFuay1iYXNlZCBhbHRlcm5hdGl2ZSkgU3BlYXJtYW4ncyByaG8KICAgIC0gKHJhbmstYmFzZWQgYWx0ZXJuYXRpdmUpIEtlbmRhbGwncyB0YXUgIAotICRSXjIkOiBjb2VmZmljaWVudCBvZiBkZXRlcm1pbmF0aW9uLS1wcm9wb3J0aW9uIG9mIHJlc3BvbnNlIHZhcmlhYmlsaXR5IGV4cGxhaW5lZCBieSB0aGUgbW9kZWwtLTAgZm9yIG5vbmUgYXQgYWxsOyAxIGZvciBwZXJmZWN0IHByZWRpY3Rpb24KCgoKIyMgQ29uZnVzaW9uIG1hdHJpeAoKLSB3ZSd2ZSBkaXNjdXNzZWQgcXVpdGUgYSBmZXcgY29uZnVzaW9uIG1hdHJpY2VzIHdoaWxlIGFzc2Vzc2luZyBtb2RlbCBwZXJmb3JtYW5jZSB3aGVuIGNsYXNzaWZ5aW5nIG91ciB0cmFpbmluZyBkYXRhLgotIExldCdzIGV2YWx1YXRlIHRoZSB0ZXN0IGRhdGEuLi4KCmBgYHtyfQojIGstTmVhcmVzdCBOZWlnaGJvcgp0ZXN0X2tubiA8LSBrbm4odHJhaW4gPSB0cmFpbl9xdWFudCwgY2wgPSB0cmFpbiRzdWljaWRlLCBrID0gNSwKICAgICAgICAgICAgICAgICAgIHRlc3QgPSBzZWxlY3QodGVzdCwgYWdlLCBjZXNkLCBhdmdBbGNvaG9sLCBwc3NfZnIpKQoKY29uZnVzaW9uIDwtIHRhbGx5KHRlc3Rfa25uIH4gc3VpY2lkZSwgZGF0YSA9IHRlc3QsIGZvcm1hdCA9ICJjb3VudCIpCmNvbmZ1c2lvbiAjIHRlc3QgZGF0YQoKc3VtKGRpYWcoY29uZnVzaW9uKSkgLyBucm93KHRlc3QpCmBgYAoKCiMjIyMgT3V0IG9mIHNhbXBsZSBtb2RlbCBjb21wYXJpc29ucyAKCi0gbG90cyBvZiB0aGVzZSBtb2RlbHMgaGF2ZSBkaWZmZXJlbnQgY2xhc3NlcywgYnV0IG1hbnkgb2YgdGhlbSBoYXZlIGEgYHByZWRpY3QoKWAgbWV0aG9kIGFzc29jaWF0ZWQKCmBgYHtyfQojIHNsaWdodCBtb2RpZmljYXRpb24gb2Ygb3VyIG51bGwgbW9kZWwgKGludGVyY2VwdC1vbmx5IGxvZ2l0IG1vZGVsKQptb2RfbnVsbCA8LSBnbG0oc3VpY2lkZSB+IDEsIGRhdGEgPSB0cmFpbiwgZmFtaWx5ID0gImJpbm9taWFsIikKCiMgc3RvcmUgb3VyIHZhcmlvdXMgbW9kZWxzIGFzIGEgbGlzdAptb2RlbHMgPC0gbGlzdChtb2RfbnVsbCwgbW9kX3RyZWUsIG1vZF90cmVlMiwgbW9kX2ZvcmVzdCwgbW9kX25uZXQsIG1vZF9uYiwgbW9kX2xvZ2l0KQoKIyAjIG1vZGVscyBhbmQgdmFyaW91cyBgcHJlZGljdCgpYCBtZXRob2RzIGF2YWlsYWJsZQojIGxhcHBseShtb2RlbHMsIEZVTiA9IGNsYXNzKQojIG1ldGhvZHMoInByZWRpY3QiKQpgYGAKCgpgYGB7ciBpbmNsdWRlPUZBTFNFLCBlY2hvPVRSVUV9CnByZWRpY3Rpb25zX3RyYWluIDwtIAogIGRhdGEuZnJhbWUoCiAgICB5ID0gYXMuY2hhcmFjdGVyKHRyYWluJHN1aWNpZGUpLCAKICAgIHR5cGUgPSAidHJhaW4iLCAKICAgIG1vZF9udWxsID0gcHJlZGljdChtb2RfbnVsbCwgdHlwZSA9ICJyZXNwb25zZSIpLCAKICAgIG1vZF90cmVlID0gcHJlZGljdChtb2RfdHJlZSwgdHlwZSA9ICJjbGFzcyIpLCAKICAgIG1vZF90cmVlMiA9IHByZWRpY3QobW9kX3RyZWUyLCB0eXBlID0gImNsYXNzIiksIAogICAgbW9kX2ZvcmVzdCA9IHByZWRpY3QobW9kX2ZvcmVzdCwgdHlwZSA9ICJjbGFzcyIpLCAKICAgIG1vZF9ubmV0ID0gcHJlZGljdChtb2Rfbm5ldCwgdHlwZSA9ICJjbGFzcyIpLCAKICAgIG1vZF9uYiA9IHByZWRpY3QobW9kX25iLCBuZXdkYXRhID0gdHJhaW4sIHR5cGUgPSAiY2xhc3MiKSwKICAgIG1vZF9sb2dpdCA9IHByZWRpY3QobW9kX2xvZ2l0LCB0eXBlID0gInJlc3BvbnNlIikpIAoKcHJlZGljdGlvbnNfdGVzdCA8LSAKICBkYXRhLmZyYW1lKAogICAgeSA9IGFzLmNoYXJhY3Rlcih0ZXN0JHN1aWNpZGUpLCAKICAgIHR5cGUgPSAidGVzdCIsIAogICAgbW9kX251bGwgPSBwcmVkaWN0KG1vZF9udWxsLCBuZXdkYXRhID0gdGVzdCwgdHlwZSA9ICJyZXNwb25zZSIpLCAKICAgIG1vZF90cmVlID0gcHJlZGljdChtb2RfdHJlZSwgbmV3ZGF0YSA9IHRlc3QsIHR5cGUgPSAiY2xhc3MiKSwgCiAgICBtb2RfdHJlZTIgPSBwcmVkaWN0KG1vZF90cmVlMiwgbmV3ZGF0YSA9IHRlc3QsIHR5cGUgPSAiY2xhc3MiKSwgCiAgICBtb2RfZm9yZXN0ID0gcHJlZGljdChtb2RfZm9yZXN0LCBuZXdkYXRhID0gdGVzdCwgdHlwZSA9ICJjbGFzcyIpLCAKICAgIG1vZF9ubmV0ID0gcHJlZGljdChtb2Rfbm5ldCwgbmV3ZGF0YSA9IHRlc3QsIHR5cGUgPSAiY2xhc3MiKSwgCiAgICBtb2RfbmIgPSBwcmVkaWN0KG1vZF9uYiwgbmV3ZGF0YSA9IHRlc3QsIHR5cGUgPSAiY2xhc3MiKSwKICAgIG1vZF9sb2dpdCA9IHByZWRpY3QobW9kX2xvZ2l0LCBuZXdkYXRhID0gdGVzdCwgdHlwZSA9ICJyZXNwb25zZSIpKSAKCnByZWRpY3Rpb25zIDwtIGJpbmRfcm93cyhwcmVkaWN0aW9uc190cmFpbiwgcHJlZGljdGlvbnNfdGVzdCkKCiMgaW5zcGVjdCBwcm9ncmVzcyAobW9kZWwgcmVzdWx0cykKZ2xpbXBzZShwcmVkaWN0aW9ucykKCiMgY2xlYW4gdXAgbnVsbCAmIGxvZ2l0IG1vZGVscwpwcmVkaWN0aW9uc190aWR5IDwtIAogIHByZWRpY3Rpb25zICU+JQogIG11dGF0ZShtb2RfbnVsbCA9IGlmZWxzZShtb2RfbnVsbCA8IDAuNSwgIm5vIiwgInllcyIpLCAKICAgICAgICAgbW9kX2xvZ2l0ID0gaWZlbHNlKG1vZF9sb2dpdCA8IDAuNSwgIm5vIiwgInllcyIpKSAlPiUKICBnYXRoZXIoa2V5ID0gIm1vZGVsIiwgdmFsdWUgPSAieV9oYXQiLCAtdHlwZSwgLXkpCgojIGluc3BlY3QgcHJvZ3Jlc3MgKHN0YWNrZWQgbW9kZWxzKQpnbGltcHNlKHByZWRpY3Rpb25zX3RpZHkpCgojIHRhYnVsYXRlCnByZWRpY3Rpb25zX3N1bW1hcnkgPC0gCiAgcHJlZGljdGlvbnNfdGlkeSAlPiUKICBncm91cF9ieShtb2RlbCwgdHlwZSkgJT4lCiAgc3VtbWFyaXNlKE4gPSBuKCksIAogICAgICAgICAgICBjb3JyZWN0ID0gc3VtKHkgPT0geV9oYXQsIDApLCAKICAgICAgICAgICAgcG9zaXRpdmVzID0gc3VtKHkgPT0gInllcyIpLCAKICAgICAgICAgICAgdHJ1ZV9wb3MgPSBzdW0oeV9oYXQgPT0gInllcyIgJiB5ID09IHlfaGF0KSwgCiAgICAgICAgICAgIGZhbHNlX3BvcyA9IHN1bSh5X2hhdCA9PSAieWVzIiAmIHkgIT0geV9oYXQpKSAKCiMgaW5zcGVjdCBwcm9ncmVzcyAoc3RhY2tlZCBtb2RlbHMpCmdsaW1wc2UocHJlZGljdGlvbnNfc3VtbWFyeSkKCnByZWRpY3Rpb25zX3N1bW1hcnkgPC0gCiAgcHJlZGljdGlvbnNfc3VtbWFyeSAlPiUKICBtdXRhdGUoYWNjdXJhY3kgPSBjb3JyZWN0IC8gTiAqIDEwMCwgCiAgICAgICAgIHRwciA9IHRydWVfcG9zIC8gcG9zaXRpdmVzLCAKICAgICAgICAgZnByID0gZmFsc2VfcG9zIC8gKE4gLSBwb3NpdGl2ZXMpKSAlPiUKICB1bmdyb3VwKCkgJT4lCiAgZ2F0aGVyKHZhbF90eXBlLCB2YWwsIC1tb2RlbCwgLXR5cGUpICU+JQogIHVuaXRlKHRlbXAxLCB0eXBlLCB2YWxfdHlwZSwgc2VwID0gIl8iKSAlPiUKICBzcHJlYWQodGVtcDEsIHZhbCkgJT4lCiAgYXJyYW5nZShkZXNjKHRlc3RfYWNjdXJhY3kpKSAlPiUKICBzZWxlY3QobW9kZWwsIHRyYWluX2FjY3VyYWN5LCB0ZXN0X2FjY3VyYWN5LCB0ZXN0X3RwciwgdGVzdF9mcHIpCgpwcmVkaWN0aW9uc19zdW1tYXJ5ICU+JQogIHNlbGVjdChtb2RlbCwgdHJhaW5fYWNjdXJhY3ksIHRlc3RfYWNjdXJhY3kpICU+JQogIGFycmFuZ2UoZGVzYyh0cmFpbl9hY2N1cmFjeSkpCmBgYAoKCgoKIyMgUmVjZWl2ZXIgb3BlcmF0aW5nIGNoYXJhY3RlcmlzdGljIChST0MpIGN1cnZlcwoKIVtmcm9tIE1EU1IgRmlndXJlIDguNiAocC4gMTkxKV0oZXhhbXBsZVJPQy5wbmcpCgotIFdlJ3ZlIG1vc3RseSBmb2N1c2VkIG9uIGNsYXNzaWZpY2F0aW9ucyBpbiB0aGUgY29udGV4dCBvZiB0aGUgYWN0dWFsIHJlc3BvbnNlIChgc3VpY2lkZWA6IHsieWVzIiwgIm5vIn0pCi0gcHJvYmFiaWxpdHkgYXNzb2NpYXRlZCB3aXRoIGVhY2ggY2xhc3NpZmljYXRpb24gaXMgYWxzbyBvZiB2YWx1ZQotIFJPQyBjdXJ2ZXMgZ3JhcGhpY2FsbHkgZGlzcGxheSB0aGUgdHJhZGUtb2ZmIGJldHdlZW4gdHJ1ZS1wb3NpdGl2ZSBhbmQgZmFsc2UtcG9zaXRpdmUgY2xhc3NpZmljYXRpb25zCi0gUTogSG93IGhhdmUgd2UgZG9uZSBvdmVyYWxsPwotIFE6IFdoYXQgd291bGQgImlkZWFsIiBsb29rIGxpa2U/CgojIyBSZWNlaXZlciBvcGVyYXRpbmcgY2hhcmFjdGVyaXN0aWMgKFJPQykgY3VydmVzCgotIFRoZSBmaWd1cmUgc2hvd3MgcHJlZGljdGlvbnMgb2YgYSBiaW5hcnkgY2xhc3NpZmllciBtb2RlbCAoZS5nLiwgIlllcyIgb3IgIk5vIiBvdXRjb21lKQotIFE6IEluIHRoZSBjb250ZXh0IG9mIG91ciBgSEVMUHJjdGAgZXhhbXBsZSwgd2hhdCBkbyB0aGUgdHdvIGRpc3RyaWJ1dGlvbnMgcmVwcmVzZW50PwotIFE6IHdoZW4gaXMgdGhlICJpZGVhbCIgYWNoaWV2ZWQ/CgoKIVtpbWFnZSBjcmVkaXQgKDIvMTMvMjAxOSk6IDxodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9SZWNlaXZlcl9vcGVyYXRpbmdfY2hhcmFjdGVyaXN0aWM+XShleHBsYWluUk9DLnBuZykKCiMjIFJlY2VpdmVyIG9wZXJhdGluZyBjaGFyYWN0ZXJpc3RpYyAoUk9DKSBjdXJ2ZXMKCi0gUTogSG93IGRpZCBvdXIgbW9kZWxzIGRvPwotIFE6IFdoaWNoIG9uZSBzZWVtcyB0byBiZSB0aGUgYmVzdAoKYGBge3J9CnJlcXVpcmUoUk9DUikKCiMgb3V0cHV0IGFyZ3VtZW50cyBjb3JyZXNwb25kaW5nIHRvIG9iamVjdHMgaW4gYG1vZGVsYCBsaXN0Cm91dHB1dHMgPC0gYygicmVzcG9uc2UiLCAicHJvYiIsICJwcm9iIiwgInByb2IiLCAicmF3IiwgInJhdyIsICJyZXNwb25zZSIpCnJvY190ZXN0IDwtIG1hcHBseShGVU4gPSBwcmVkaWN0LCBtb2RlbHMsIHR5cGUgPSBvdXRwdXRzLCBNb3JlQXJncyA9IGxpc3QobmV3ZGF0YSA9IHRlc3QpKSAlPiUKICBhcy5kYXRhLmZyYW1lKCkgJT4lCiAgc2VsZWN0KDEsIDMsIDUsIDcsIDgsIDEwLCAxMSkKCm5hbWVzKHJvY190ZXN0KSA8LSBjKCJtb2RfbnVsbCIsICJtb2RfdHJlZSIsICJtb2RfdHJlZTIiLCAibW9kX2ZvcmVzdCIsICJtb2Rfbm5ldCIsICJtb2RfbmIiLCAibW9kX2xvZ2l0IikKCmdsaW1wc2Uocm9jX3Rlc3QpCgpyb2NfdGlkeSA8LSAKICByb2NfdGVzdCAlPiUKICBnYXRoZXIoa2V5ID0gIm1vZGVsIiwgdmFsdWUgPSAieV9oYXQiKSAlPiUKICBncm91cF9ieShtb2RlbCkgJT4lCiAgZHBseXI6OmRvKGdldF9yb2MoLiwgeSA9IHRlc3Qkc3VpY2lkZSkpCgojIHBsb3QgUk9DIGN1cnZlcwpyb2NfdGlkeSAlPiUKICBnZ3Bsb3QoYWVzKHggPSBmcHIsIHkgPSB0cHIpKSArIAogIGdlb21fbGluZShhZXMoY29sb3IgPSBtb2RlbCkpICsgCiAgZ2VvbV9hYmxpbmUoaW50ZXJjZXB0ID0gMCwgc2xvcGUgPSAxLCBsdHkgPSAzKSArIAogIHlsYWIoIlRydWUgcG9zaXRpdmUgcmF0ZSAoc2Vuc2l0aXZpdHkpIikgKyAKICB4bGFiKCJGYWxzZSBwb3NpdGl2ZSByYXRlICgxIC0gc3BlY2lmaWNpdHkpIikgKyAKICBnZW9tX3BvaW50KGRhdGEgPSBwcmVkaWN0aW9uc19zdW1tYXJ5LCBzaXplID0gMywgCiAgICAgICAgICAgICBhZXMoeCA9IHRlc3RfZnByLCB5ID0gdGVzdF90cHIsIGNvbG9yID0gbW9kZWwpKQpgYGAKCgoKCgojIyBCaWFzLXZhcmlhbmNlIHRyYWRlb2ZmCgohW2ltYWdlIGNyZWRpdDogSmFtZXMgZXQgYWwgKDIwMTMpIDxodHRwOi8vd3d3LWJjZi51c2MuZWR1L35nYXJldGgvSVNMLz5dKGJpYXNWYXJpYW5jZS5wbmcpCgpGb3IgYSBnaXZlbiB0ZXN0IHZhbHVlLCAkeF8wJDoKCiQkRSh5XzAgLSBcaGF0e2Z9KHhfMCkpXjIgPSBcdGV4dHtWYXJ9KFxoYXR7Zn0oeF8wKSkgKyBbXHRleHR7Qmlhc30oXGhhdHtmfSh4XzApKV1eMiArIFx0ZXh0e1Zhcn0oXGVwc2lsb24pJCQKCi0gVGhlIGV4cGVjdGVkIHZhcmlhYmlsaXR5IG9mIHRoZSAqKnRlc3Qgc2V0IHByZWRpY3Rpb25zKiogaXMgYSBzdW0gb2YgdGhyZWUgcXVhbnRpdGllcwogICAgLSBSYW5kb21uZXNzIChmcm9tIG5hdHVyZTsgb3VyIHNvLWNhbGxlZCBlcnJvciB0ZXJtKQogICAgLSBCaWFzIChmcm9tIHVuZGVyLWZpdHRpbmcgdGhlIGRhdGEpCiAgICAtIFZhcmlhbmNlIChmcm9tIG92ZXItZml0dGluZyB0aGUgZGF0YSkKLSBDb25zaWRlciB0aGUgZmlndXJlIGFib3ZlLiAgVGhlIEJsYWNrIGN1YmljIGN1cnZlIGlzIHRoZSB0cnVlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIFkgYW5kIFggdXNlZCB0byBnZW5lcmF0ZSB0aGUgZGF0YS4KLSAqKkJpYXMqKiBoZXJlIHJlZmVycyB0byB0aGUgYSBjb25zaXN0ZW50IHRlbmRlbmN5IG9mIGEgc3RhdGlzdGljYWwgbW9kZWwgdG8gb3Zlci0gb3IgdW5kZXItZXN0aW1hdGUgdHJ1ZSBwb3B1bGF0aW9uIHBhcmFtZXRlcnMgKGkuZS4gdGhlIG5hdHVyZSBvZiB0aGUgcHJvY2VzcyB0aGF0IGdlbmVyYXRlZCB0aGUgZGF0YSkuICBJbiB0aGUgZmlndXJlLCAKICAgIC0gVGhlIE9yYW5nZSBsaW5lYXIgbW9kZWwgaXMgaGlnaGx5IGJpYXNlZCBiZWNhdXNlLS1yb3VnaGx5IHNwZWFraW5nLS10aGUgbW9kZWwKICAgICAgICAtIGNvbnNpc3RlbnRseSBvdmVyLWVzdGltYXRlcyBZIHdoZW4gWCBpcyBiZXR3ZWVuIDAgYW5kIDQwCiAgICAgICAgLSB0aGVuIGNvbnNpc3RlbnRseSB1bmRlcmVzdGltYXRlcyBZIGZvciBYIGJldHdlZW4gNDAgYW5kIDcwCiAgICAgICAgLSBhbmQgdGhlbiBvdmVyZXN0aW1hdGVzIFkgYWdhaW4gZm9yIFggZ3JlYXRlciB0aGFuIDcwCiAgICAtIEluIHNob3J0LCB0aGUgbGluZWFyIG1vZGVsIGZhaWxzIHRvIHByb3Blcmx5IHJlZmxlY3QgdGhlIHJlbGF0aW9uc2hpcCAoaS5lLiwgY29uZGl0aW9uYWwgZXhwZWN0YXRpb24pIGJldHdlZW4gdGhlIHJlc3BvbnNlIChZKSBhbmQgdGhlIGV4cGxhbmF0b3J5IHZhcmlhYmxlcyAoWCdzKS4gIEFzIGEgcmVzdWx0LCBzb21lIG9mIHRoZSBzdHJ1Y3R1cmFsIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIFkgYW5kIFgncyBpcyBpbmNvcnJlY3RseSB0cmVhdGVkIGxpa2UgcmFuZG9tbmVzcy4KICAgIC0gVGhlIEdyZWVuIG1vZGVsIHRlbmRzIHRvIGNsb3NlbHkgZm9sbG93IHRoZSBkYXRhLCBzbyBpdCBoYXMgbG93ZXIgYmlhcwogICAgLSBJbiB0aGUgZ3JlZW4gd2lnZ2x5IG1vZGVsIHRlbmRzIHRvIGNsb3NlbHkgZm9sbG93IHRoZSAgCi0gKipWYXJpYW5jZSoqIGhlcmUgcmVmZXJzIHRvIGhvdyBtdWNoIG91ciBtb2RlbCB3b3VsZCBjaGFuZ2UgaWYgd2UgaGFkIGVzdGltYXRlZCBpdCB3aXRoIGEgZGlmZmVyZW50IHRyYWluaW5nIHNldC4gIEluIHRoZSBmaWd1cmUsIAogICAgLSBUaGUgR3JlZW4gd2lnZ2x5IG1vZGVsIGZvbGxvd3MgdGhlIG9ic2VydmF0aW9ucyB0b28gY2xvc2VseQogICAgICAgIC0gSWYgb25lIChvciBhIGZldykgdHJhaW5pbmcgb2JzZXJ2YXRpb25zIHdlcmUgY2hhbmdlZCwgd2UgZXhwZWN0IGEgc3Vic3RhbnRpYWwgaW1wYWN0IG9uIHRoZSBtb2RlbCAKICAgIC0gVGhlIE9yYW5nZSBtb2RlbCB3b3VsZCBub3QgY2hhbmdlIG11Y2ggaWYgb25lIG9yIGEgZmV3IHRyYWluaW5nIG9ic2VydmF0aW9ucyB3ZXJlIGNoYW5nZWQsIHNvIGl0IGhhcyBsb3dlciB2YXJpYW5jZQoKCgoKIyMgUmVndWxhcml6YXRpb24vU2hyaW5rYWdlIChSaWRnZSBSZWdyZXNzaW9uICYgTGFzc28pCgotICoqR29hbCoqOiBzYWNyaWZpY2UgYSBzbWFsbCBhbW91bnQgb2YgYmlhcyB0byBkZWNyZWFzZSB2YXJpYW5jZQogICAgLSBFc3BlY2lhbGx5IHVzZWZ1bCB3aGVuIG51bWJlciBvZiBleHBsYW5hdG9yeSB2YXJpYWJsZXMgaXMgbGFyZ2UgKHBlcmhhcHMgbGFyZ2VyIHRoYW4gbiEpIGFuZC9vciB3aGVuIHBhcmFtZXRlciBlc3RpbWF0ZXMgaGF2ZSBoaWdoIHZhcmlhbmNlCi0gKipNZXRob2QqKjogaW1wb3NlIGEgY29uc3RyYWludCB0aGF0IGludGVudGlvbmFsbHkgYmlhc2VzIHBhcmFtZXRlciBlc3RpbWF0ZXMgKGUuZy4gc2xvcGVzIGluIHJlZ3Jlc3Npb24pIHRvd2FyZCB6ZXJvIGluIG9yZGVyIHRvIHJlZHVjZSB2YXJpYW5jZQotIHJlY2FsbDogaW4gUmVncmVzc2lvbiB3ZSBmaXQgb3VyIG1vZGVsIGJ5IG9wdGltaXppbmcgc29tZSBkaXN0YW5jZSBtZXRyaWMgKGUuZy4sIHN1bSBvZiBzcXVhcmVkIGVycm9ycy0tU1NFKQotIHJlZ3VsYXJpemF0aW9uL3Nocmlua2FnZSBtZXRob2RzIHNpbXBseSBtb2RpZnkgdGhlIHF1YW50aXR5IHRoYXQgd2Ugb3B0aW1pemUgCiAgICAtIFJpZGdlIHJlZ3Jlc3Npb246IG1pbmltaXplICRcdGV4dHtTU0V9ICsgXGxhbWJkYSBcc3VtX3tqID0gMX1ecCBcYmV0YV9qXjIkCiAgICAtIExhc3NvOiBtaW5pbWl6ZSAkXHRleHR7U1NFfSArIFxsYW1iZGEgXHN1bV97aiA9IDF9XnAgfCBcYmV0YV9qIHwkCi0gaW1wb3J0YW50IGRpZmZlcmVuY2U6IAogICAgLSBSaWRnZSByZWdyZXNzaW9uIG1vZGVsIGluY2x1ZGVzIGFsbCBwYXJhbWV0ZXJzLCBzbyB0aGVyZSBpcyBubyB2YXJpYWJsZSBzZWxlY3Rpb24KICAgIC0gTGFzc28gaGFzIGJ1aWx0LWluIHZhcmlhYmxlIHNlbGVjdGlvbiBieSBmb3JjaW5nIHNvbWUgb2YgdGhlICRcYmV0YV9qJCdzIHRvIGJlIGV4YWN0bHkgemVybwotICoqVHVuaW5nIHBhcmFtZXRlcioqOiAkXGxhbWJkYSQgCiAgICAtIHdoZW4gdGhlIHR1bmluZyBwYXJhbWV0ZXIgJFxsYW1iZGEkIGlzIHplcm8sIHRoZSByZXN1bHQgaXMgdGhlIHVzdWFsIGxlYXN0IHNxdWFyZXMgcmVncmVzc2lvbiBtb2RlbAogICAgLSB3aGVuIHRoZSB0dW5pbmcgcGFyYW1ldGVyICRcbGFtYmRhJCBpcyB2ZXJ5IGxhcmdlLCB0aGUgcmVzdWx0IGlzIGEgbnVsbCBtb2RlbCAoaW50ZXJjZXB0IG9ubHkpCiAgICAtIHByb3BlciBzZWxlY3Rpb24gaXMgaW1wb3J0YW50CiAgICAtIGNyb3NzLXZhbGlkYXRpb24gaXMgYSBwb3B1bGFyIG1ldGhvZCBmb3Igc2V0dGluZyBsYW1iZGEgKGUuZy4gbGVhdmUtb25lLW91dCkKLSBSIGZ1bmN0aW9uOiBgZ2xtbmV0OjpnbG1uZXQoKWAKICAgIC0gZnVuY3Rpb24gYXJndW1lbnQgYGFscGhhID0gMGAgZm9yIHJpZGdlIHJlZ3Jlc3Npb24KICAgIC0gZnVuY3Rpb24gYXJndW1lbnQgYGFscGhhID0gMWAgZm9yIExhc3NvCiAgICAtIGZpdHMgbGluZWFyLCBsb2dpc3RpYywgYW5kIG90aGVyIHJlZ3Jlc3Npb24gbW9kZWxzCgoKIyMgUmVndWxhcml6YXRpb24vU2hyaW5rYWdlIChSaWRnZSBSZWdyZXNzaW9uICYgTGFzc28pCgotIFE6IFdoYXQgZG8geW91IG5vdGUgYWJvdXQgY29tcGFyaXNvbiBvZiAqY29lZmZpY2llbnQgZXN0aW1hdGVzKiAod2l0aCBsb2dpc3RpYyBtb2RlbCk/CgoKYGBge3J9CnJlcXVpcmUoZ2xtbmV0KQoKdHJhaW5fbWF0cml4IDwtIAogIHRyYWluX3F1YW50ICU+JQogIG11dGF0ZShtYWxlID0gaWZlbHNlKHRyYWluJHNleCA9PSAibWFsZSIsIDEsIDApKSAlPiUKICBhcy5tYXRyaXgoKQoKIyBmaXQgbW9kZWwKbW9kX2xhc3NvIDwtIGdsbW5ldCh4ID0gdHJhaW5fbWF0cml4LCB5ID0gdHJhaW4kc3VpY2lkZSwgZmFtaWx5ID0gImJpbm9taWFsIiwgYWxwaGEgPSAxKSAgCgojIHBsb3QgY29lZmZpY2llbnRzIGFzIGEgZnVuY3Rpb24gb2YgInBlbmFsdHkiIGltcG9zZWQgYnkgdHVuaW5nIHBhcmFtZXRlcgpwbG90KG1vZF9sYXNzbykKCiMgY2hvb3NpbmcgbGFtYmRhCmN2X3Jlc3VsdCA8LSBjdi5nbG1uZXQoeCA9IGFzLm1hdHJpeCh0cmFpbl9xdWFudCksIHkgPSB0cmFpbiRzdWljaWRlLCBmYW1pbHkgPSAiYmlub21pYWwiLCB0eXBlLm1lYXN1cmUgPSAiY2xhc3MiKQpwbG90KGN2X3Jlc3VsdCkKCmJlc3RfbGFtYmRhIDwtIGN2X3Jlc3VsdCRsYW1iZGEubWluCgoKIyBsYXNzbyBjb2VmZmljaWVudCBlc3RpbWF0ZXMgKG5vdGUgc2hyaW5rYWdlOyBzZXgvZmVtYWxlIHZhcmlhYmxlIGRyb3BwZWQpCnByZWRpY3QobW9kX2xhc3NvLCB0eXBlID0gImNvZWZmaWNpZW50cyIsIHMgPSBiZXN0X2xhbWJkYSkKCiMgbG9naXN0aWMgcmVncmVzc2lvbiBjb2VmZmljaWVudCBlc3RpbWF0ZXMKbXN1bW1hcnkobW9kX2xvZ2l0KQoKYGBgCgojIyBSZWd1bGFyaXphdGlvbi9TaHJpbmthZ2UgKFJpZGdlIFJlZ3Jlc3Npb24gJiBMYXNzbykKCi0gUTogV2hhdCBkbyB5b3Ugbm90ZSBhYm91dCBjb21wYXJpc29uIG9mICp0cmFpbmluZyBhY2N1cmFjeSogKHdpdGggbG9naXN0aWMgbW9kZWwpPwoKCmBgYHtyfQoKIyB0cmFpbmluZyBhY2N1cmFjeQpzdWljaWRlX2xhc3NvUHJvYiA8LSBwcmVkaWN0KG1vZF9sYXNzbywgcyA9IGJlc3RfbGFtYmRhLCBuZXd4ID0gdHJhaW5fbWF0cml4LCB0eXBlID0gInJlc3BvbnNlIikKCnN1aWNpZGVfbGFzc28gPC0gaWZlbHNlKHN1aWNpZGVfbGFzc29Qcm9iID4gMC41LCB5ZXMgPSAieWVzIiwgIm5vIikKCmNvbmZ1c2lvbiA8LSB0YWxseShzdWljaWRlX2xhc3NvIH4gc3VpY2lkZSwgZGF0YSA9IHRyYWluLCBmb3JtYXQgPSAiY291bnQiKQpjb25mdXNpb24KCmxhc3NvX2FjYyA8LSBzdW0oZGlhZyhjb25mdXNpb24pKSAvIG5yb3codHJhaW4pICogMTAwCgojIExvZ2lzdGljIHJlZ3Jlc3Npb24gdHJhaW5pbmcgYWNjdXJhY3kgd2l0aC93aXRob3V0IHJlZ3VsYXJpemF0aW9uCmxhc3NvX2FjYyAgIyBSZWd1bGFyaXphdGlvbiAoTGFzc28pCmxvZ2l0X2FjYyAgIyBObyByZWd1bGFyaXphdGlvbgpgYGAKCgoKCjwhLS0gIyMgSG93IHdlbGwgZGlkIHRoZSBsb2dpc3RpYyBtb2RlbCBjbGFzc2lmeSBzdWljaWRlIHJpc2s/IC0tPgoKPCEtLSAtIHJlY2FsbCBvdXIgbWV0aG9kIHRvIGNvbnN0cnVjdCBhIHN5c3RlbWF0aWMgZ3JpZCBhcHByb3hpbWF0aW5nIGFsbCBwb3NzaWJsZSBvdXRjb21lcyBpbiB0aGUgZGF0YSAtLT4KPCEtLSAtIHVzZSBvdXIgbW9kZWwgdG8gcHJlZGljdCB0aGUgcmVzdWx0IGZvciBlYWNoIGNvbWJpbmF0aW9uIG9mIFgncyAtLT4KPCEtLSAgICAgLSBgbW9kZWxyOjpkYXRhX2dyaWQoKWAgaXMgY29udmVuaWVudCB0byBidWlsZCB0aGUgZ3JpZCAtLT4KPCEtLSAgICAgLSBgbW9kZWxyOjphZGRfcHJlZGljdGlvbnMoKWAgLS0+Cgo8IS0tIGBgYHtyfSAtLT4KPCEtLSAjIHNldCBncmlkIHJlc29sdXRpb24gZm9yIGVhY2ggdmFyaWFibGUgLS0+CjwhLS0gcmVzIDwtIDMwIC0tPgoKPCEtLSAjIG1ha2UgdGhlIGdyaWQgLS0+CjwhLS0gZmFrZV9ncmlkIDwtIC0tPgo8IS0tICAgdHJhaW4gJT4lIC0tPgo8IS0tICAgZGF0YV9ncmlkKCAtLT4KPCEtLSAgICAgYWdlID0gc2VxX3JhbmdlKGFnZSwgbiA9IHJlcyksIC0tPgo8IS0tICAgICBjZXNkID0gc2VxX3JhbmdlKGNlc2QsIG4gPSByZXMpLCAtLT4KPCEtLSAgICAgc2V4LCAtLT4KPCEtLSAgICAgYXZnQWxjb2hvbCA9IHNlcV9yYW5nZShhdmdBbGNvaG9sLCBuID0gcmVzKSwgLS0+CjwhLS0gICAgIHBzc19mciA9IHNlcV9yYW5nZShwc3NfZnIsIG4gPSByZXMpIC0tPgo8IS0tICAgKSAtLT4KCjwhLS0gbnJvdyhmYWtlX2dyaWQpICAjIHRoaXMgZ2V0cyBiaWcgZmFzdCBkZXBlbmRpbmcgb24gYHJlc2AuLi4gLS0+CjwhLS0gYGBgIC0tPgoKPCEtLSAjIyMgYWRkIHByZWRpY3Rpb25zIC0tPgoKPCEtLSBgYGB7cn0gLS0+CjwhLS0geV9oYXRzIDwtIC0tPgo8IS0tICAgZmFrZV9ncmlkICU+JSAtLT4KPCEtLSAgIG11dGF0ZSh5X2hhdCA9IHByZWRpY3QobW9kX2xvZ2l0LCBuZXdkYXRhID0gLiwgdHlwZSA9ICJyZXNwb25zZSIpKSAtLT4KCjwhLS0gIyBjb25mdXNpb24gbWF0cml4IC0tPgo8IS0tIHRhbGx5KHRyYWluIH4geV9oYXRzKSAtLT4KPCEtLSBgYGAgLS0+CgoKCg==

MDSR Ch 8: Supervised Learning

Announcements

MDSR Ch 8 Errata / Tips

“Learning”

Supervised Learning

Reinforcement Learning

Unsupervised Learning

Statistical Learning

Regression vs Classification

Health Evaluation and Linkage to Primary Care Study

HELPstudy Data

Variables of interest

Data Preparation

Training & Test sets

Inspecting the HELPstudy (training) data

Null model

Decision Trees

Decision tree (simple)

visualize first split for depression & suicide ideation model

Decision tree (complete)

Decision tree (partykit)

Branching and pruning

Model accuracy: Confusion matrix

Changing the control parameter

Optimal decision tree

Forests

Random Forests

Bagging

Random Forests (importance)

Boosting

K-Nearest Neighbor

KNN classifier

How (not) to choose k?

choice of k

Naive Bayes

Bayes Theorem:

P(suicide = “yes” | sex = “male”)

P(suicide = “yes” | sex = “male”)

Naive Bayes

Artificial Neural Networks

Logistic regression model

Aside: Support Vector Machines

How have we done so far?

Ensemble methods

Ensemble Models

Model Evaluation

Cross-validation

Prediction error

Confusion matrix

Out of sample model comparisons

Receiver operating characteristic (ROC) curves

Receiver operating characteristic (ROC) curves

Receiver operating characteristic (ROC) curves

Bias-variance tradeoff

Regularization/Shrinkage (Ridge Regression & Lasso)

Regularization/Shrinkage (Ridge Regression & Lasso)

Regularization/Shrinkage (Ridge Regression & Lasso)

`HELPstudy` Data

Inspecting the `HELPstudy` (training) data

P(`suicide` = “yes” | `sex` = “male”)

P(`suicide` = “yes” | `sex` = “male”)